Euler's Totient Function φ(n)

Count the units modulo n with the prime-power product formula.

The idea

Euler's totient function $\varphi(n)$ counts the integers from $1$ to $n$ that are coprime to $n$: $\varphi(n) = \#\{\, a : 1 \le a \le n, \ \gcd(a, n) = 1 \,\}.$ These are exactly the residues with a multiplicative inverse modulo $n$, called the units, so $\varphi(n)$ counts the residues we can divide by.

Two values follow directly from the definition. A prime $p$ is coprime to every smaller positive integer, so $\varphi(p) = p - 1$. A prime power $p^{k}$ shares a factor only with the multiples of $p$, and there are $p^{k-1}$ of those up to $p^{k}$, so $\varphi(p^{k}) = p^{k} - p^{k-1}$.

Every other value follows from one property: $\varphi$ is multiplicative, meaning $\varphi(mn) = \varphi(m)\,\varphi(n)$ whenever $\gcd(m, n) = 1$. Split $n$ into its prime powers, apply the prime-power rule to each, and multiply. The result condenses to $\varphi(n) = n \prod_{p \mid n}\left(1 - \frac{1}{p}\right),$ with one factor for each distinct prime dividing $n$, whatever exponent it carries. In the strip $1$ to $n$, the multiples of a prime $p$ make up a $\tfrac{1}{p}$ share; striking them out, and then the multiples of a second prime $q$, leaves the fraction $\left(1 - \tfrac{1}{p}\right)\left(1 - \tfrac{1}{q}\right)$ surviving.

Ways to work on it

• Walkthrough. Coprime counts, primes, and the multiplicative product formula.
• Practice. Totient a number with the product formula.
• Hardest. Totient a multi-prime modulus and apply Euler's theorem.

Not sure where to start? Take the ten-question placement test.