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.
More Worked Examples
Example 1: a prime, φ(13)
13 is prime, so its only prime factor is 13 itself:
\(\varphi(13) = 13\left(1-\frac{1}{13}\right) = 13 \cdot \frac{12}{13} = \)12. This matches the prime shortcut \(\varphi(p) = p-1\).
Example 2: a prime power, φ(32)
Factor: \(32 = 2^5\). The only distinct prime is 2.
\(\varphi(32) = 32\left(1-\frac{1}{2}\right) = 32 \cdot \frac{1}{2} = \)16.
Equivalent prime-power form: \(\varphi(p^k) = p^k - p^{k-1}\), so \(\varphi(2^5) = 2^5 - 2^4 = 32 - 16 = 16\). These are exactly the odd numbers from 1 to 31.
Example 3: three or more distinct primes, φ(210)
Factor: \(210 = 2 \cdot 3 \cdot 5 \cdot 7\).
- Start with \(210\).
- Multiply by \(1-\frac{1}{2} = \frac{1}{2}\): \(210 \cdot \frac{1}{2} = 105\).
- Multiply by \(1-\frac{1}{3} = \frac{2}{3}\): \(105 \cdot \frac{2}{3} = 70\).
- Multiply by \(1-\frac{1}{5} = \frac{4}{5}\): \(70 \cdot \frac{4}{5} = 56\).
- Multiply by \(1-\frac{1}{7} = \frac{6}{7}\): \(56 \cdot \frac{6}{7} = 48\).
So \(\varphi(210) = \)48. Note that the product rule only uses each distinct prime once. For example, \(60 = 2^2 \cdot 3 \cdot 5\) gives \(60 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} = 16\).
Interpreting φ(n) and Its Uses
- Primality link: for \(n \ge 2\), \(\varphi(n) = n-1\) if and only if \(n\) is prime. Every number below a prime is coprime to it. If \(n\) is composite, at least one number below it shares a factor, so \(\varphi(n) < n-1\).
- Group of units: \(\varphi(n)\) is the number of elements in the group of units modulo \(n\), i.e. the residues that have a multiplicative inverse mod \(n\). For \(n = 15\) these are 1, 2, 4, 7, 8, 11, 13, 14, which gives 8 elements.
- Euler's theorem: if \(\gcd(a, n) = 1\), then \(a^{\varphi(n)} \equiv 1 \pmod{n}\). Example: \(a = 2\), \(n = 15\), \(\varphi(15) = \)8, and \(2^8 = 256 = 17 \cdot 15 + 1 \equiv 1 \pmod{15}\). Fermat's little theorem is the special case \(n = p\) prime.
- RSA: when \(n = pq\) for distinct primes \(p\) and \(q\), \(\varphi(n) = (p-1)(q-1)\). With \(n = 15 = 3 \cdot 5\): \(\varphi(15) = 2 \cdot 4 = 8\). The public exponent \(e\) must be coprime to \(\varphi(n)\), and the private exponent \(d\) satisfies \(ed \equiv 1 \pmod{\varphi(n)}\). Real RSA uses primes hundreds of digits long. Anyone who can factor \(n\) can compute \(\varphi(n)\), which is why security rests on factoring being hard.
- The ratio depends only on distinct primes: \(\dfrac{\varphi(n)}{n} = \prod_{p \mid n}\left(1-\frac{1}{p}\right)\). Exponents do not matter. For example, 6 and 12 both have prime set {2, 3}, so \(\varphi(6)/6 = 2/6 = 1/3\) and \(\varphi(12)/12 = 4/12 = 1/3\).
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.