Euler's Totient Function
To generalise Fermat's theorem beyond primes we need to count something: how many numbers below
n are coprime
to it. That count is Euler's totient function,
\varphi(n) — the size of the set of "invertible" residues, and one of
the most important functions in number theory.
Definition
\varphi(n) = \#\{\,1 \le a \le n : \gcd(a, n) = 1\,\}.
For n = 12, the numbers coprime to it are
1, 5, 7, 11 — four of them — so
\varphi(12) = 4. These are exactly the residues with a
modular inverse,
the "units" of \mathbb{Z}_n.
A formula from the prime factorisation
Two facts make \varphi easy to compute:
-
For a prime p: every number
1, \dots, p-1 is coprime to it, so
\varphi(p) = p - 1. For a prime power,
\varphi(p^k) = p^k - p^{k-1} = p^{k}\!\left(1 - \tfrac1p\right).
-
It is multiplicative: if \gcd(m, n) = 1 then
\varphi(mn) = \varphi(m)\varphi(n) — a consequence of the
Chinese Remainder Theorem.
Putting them together gives the product formula over the distinct primes dividing n:
\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right).
\varphi(12) = 12\left(1 - \tfrac12\right)\left(1 - \tfrac13\right) = 12 \cdot \tfrac12 \cdot \tfrac23 = 4. \checkmark
The case that builds RSA
The single most important value: for two distinct primes p and
q,
\varphi(pq) = (p-1)(q-1).
Anyone who knows p and q can compute this
instantly; anyone who knows only the product n = pq cannot — computing
\varphi(n) is as hard as factoring. That asymmetry is precisely the
trapdoor RSA is built on, via
Euler's theorem.