What is Euler's Totient Function?
Euler's totient function, written \(\varphi(n)\), counts how many positive integers from 1 up to n share no common factor with n other than 1 — that is, the integers that are coprime to n. For example, \(\varphi(9) = 6\) because 1, 2, 4, 5, 7 and 8 are all coprime to 9. The function is fundamental in number theory and appears throughout cryptography, most famously in the RSA algorithm where \(\varphi(n)\) determines the modular inverse used to generate keys.
How to use this calculator
Enter any positive integer n and press calculate. The tool factors n into its distinct prime divisors and applies the product formula to return \(\varphi(n)\) instantly, along with the list of distinct primes it found. It works for both small numbers and very large ones up to a billion.
The formula explained
The efficient way to compute the totient is the product formula:
$$\varphi(n) = n \cdot \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$$taken over every distinct prime \(p\) that divides n.
You only need the distinct primes, not their multiplicities. Each factor \(\left(1 - \frac{1}{p}\right)\) trims away the fraction of numbers divisible by that prime.
Worked example
Take \(n = 36\). Its prime factorization is \(2^2 \times 3^2\), so the distinct primes are 2 and 3. Then:
$$\varphi(36) = 36 \times \left(1 - \frac{1}{2}\right) \times \left(1 - \frac{1}{3}\right) = 36 \times \frac{1}{2} \times \frac{2}{3} = 36 \times \frac{1}{3} = \mathbf{12}$$So exactly 12 integers between 1 and 36 are coprime to 36.
FAQ
What is \(\varphi(1)\)? By convention \(\varphi(1) = 1\), since 1 is coprime to itself.
What is \(\varphi\) of a prime p? For any prime p, \(\varphi(p) = p - 1\), because every integer from 1 to \(p-1\) is coprime to p.
Is \(\varphi\) multiplicative? Yes. If \(\gcd(a, b) = 1\) then \(\varphi(a \cdot b) = \varphi(a) \cdot \varphi(b)\), which is exactly why the product over distinct primes works.
