Mod a prime $p$, all $p - 1$ nonzero residues have inverses. Mod a composite, only some do: the ones coprime to $n$. Counting them is the job of Euler's phi function, and the count is what replaces $p - 1$ when we generalize Fermat's theorem.
Definition. $\varphi(n)$ is the number of integers $k$ with $1 \le k \le n$ and $\gcd(k, n) = 1$. For example, mod 12 the numbers coprime to 12 are $1, 5, 7, 11$, so $\varphi(12) = 4$. These are the units mod $n$, the residues with inverses.
Formulas. For a prime $p$: $\varphi(p) = p - 1$ and $\varphi(p^{k}) = p^{k} - p^{k-1}$. If $\gcd(m, n) = 1$, then $\varphi(mn) = \varphi(m)\varphi(n)$. Together, with the prime factorization of $n$: $$\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right).$$
Why it works
Coprime products. By the Chinese Remainder Theorem, each $x$ mod $mn$ matches exactly one pair ($x \bmod m$, $x \bmod n$), and $x$ is coprime to $mn$ exactly when both parts are coprime to their moduli. So the units mod $mn$ match the pairs of units, and there are $\varphi(m)\varphi(n)$ pairs.
| $k$ mod 12 | 1 | 5 | 7 | 11 |
|---|---|---|---|---|
| mod 4 | 1 | 1 | 3 | 3 |
| mod 3 | 1 | 2 | 1 | 2 |
Worked example: A prime power times another
- $36 = 2^{2} \cdot 3^{2}$, with coprime factors $4$ and $9$.
- $\varphi(4) = 4 - 2 = 2$ and $\varphi(9) = 9 - 3 = 6$.
- $\varphi(36) = 2 \cdot 6 = 12$. Same by the product formula: $36 \cdot \frac{1}{2} \cdot \frac{2}{3} = 12$.
Answer: $12$.
Worked example: Three primes
- $1001 = 7 \cdot 11 \cdot 13$.
- $\varphi(1001) = 6 \cdot 10 \cdot 12 = 720$.
Answer: $720$.
Worked example: Fractions in lowest terms
- $\frac{k}{12}$ is in lowest terms exactly when $\gcd(k, 12) = 1$.
- So the count is $\varphi(12) = 4$: $\frac{1}{12}, \frac{5}{12}, \frac{7}{12}, \frac{11}{12}$.
Answer: $4$.
| $n$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $\varphi(n)$ | 1 | 1 | 2 | 2 | 4 | 2 | 6 | 4 | 6 | 4 | 10 | 4 |
Common mistake
Key idea