Euler’s Theorem

Euler’s theorem is the engine inside RSA. It says: if you live in $\mathbb{Z}/n\mathbb{Z}$ and you are coprime to $n$, then raising yourself to the power $\phi(n)$ lands you exactly back on $1$. That single identity — first proved by Euler in 1763 — is what makes RSA decryption work: the recipient’s private exponent $d$ is chosen so that $ed \equiv 1 \pmod{\phi(n)}$, and Euler’s theorem then guarantees $(m^e)^d \equiv m \pmod{n}$. Beyond RSA, Euler’s theorem powers pseudo-random number generators, primality tests, and the entire theory of finite cyclic groups.

Euler’s totient $\phi(n)$

The Euler totient $\phi(n)$ counts the integers $k$ with $1 \leq k \leq n$ and $\gcd(k, n) = 1$. These are exactly the units of $\mathbb{Z}/n\mathbb{Z}$ — the elements that have multiplicative inverses. Examples: $\phi(1) = 1$, $\phi(5) = 4$ (namely $1, 2, 3, 4$), $\phi(12) = 4$ (namely $1, 5, 7, 11$).

Computing $\phi$ from the prime factorisation. $\phi$ is multiplicative: if $\gcd(m, n) = 1$, then $\phi(mn) = \phi(m) \phi(n)$. Combined with $\phi(p^k) = p^k - p^{k-1} = p^{k-1}(p - 1)$ for prime $p$, this gives a formula for every $n$: factor $n = p_1^{a_1} \cdots p_r^{a_r}$ and compute $\phi(n) = \prod_i p_i^{a_i - 1}(p_i - 1)$. Example: $\phi(360) = \phi(2^3 \cdot 3^2 \cdot 5) = 4 \cdot 6 \cdot 4 = 96$.

The group $(\mathbb{Z}/n\mathbb{Z})^\times$

The set $U_n$ of units of $\mathbb{Z}/n\mathbb{Z}$ is closed under multiplication: if $a, b$ are both coprime to $n$, so is $ab$. It contains $1$, and every unit has an inverse (that is the definition). So $U_n$ is a finite abelian group of order $\phi(n)$, often written $(\mathbb{Z}/n\mathbb{Z})^\times$. The mapping below illustrates how multiplication-by-a fixed unit $a$ permutes $U_n$:

(The mapping-arrows widget visualises a function between two sets. Mentally label the left column with the units of $\mathbb{Z}/n\mathbb{Z}$ and the right column with the same set; an arrow from $x$ to $a \cdot x \bmod n$ shows multiplication-by-$a$ as a permutation. Because $a$ is a unit, every element on the right is hit exactly once.)

Euler’s theorem

If $\gcd(a, n) = 1$, then $a^{\phi(n)} \equiv 1 \pmod{n}$.

Sketch of proof. Let $r_1, r_2, \ldots, r_{\phi(n)}$ be the units of $\mathbb{Z}/n\mathbb{Z}$. Multiplication by $a$ permutes them (because $a$ is a unit). So ${a r_1, a r_2, \ldots, a r_{\phi(n)}} = {r_1, r_2, \ldots, r_{\phi(n)}}$ as sets. Take the product of both sides: $a^{\phi(n)} \cdot \prod r_i \equiv \prod r_i \pmod{n}$. The product $\prod r_i$ is itself a unit, so we may cancel it: $a^{\phi(n)} \equiv 1 \pmod{n}$.

Fermat’s little theorem — the special case $n = p$

When $n = p$ is prime, $\phi(p) = p - 1$. Euler’s theorem becomes: if $p \nmid a$, then $a^{p-1} \equiv 1 \pmod{p}$. Equivalently, $a^p \equiv a \pmod{p}$ for all integers $a$ (just multiply by $a$ if $p \mid a$). This is Fermat’s little theorem, the prototype primality-test: pick a random $a$, compute $a^{n-1} \bmod n$, and if you get anything other than $1$, $n$ is definitely composite.

Pause and think: Why does Euler’s theorem require $\gcd(a, n) = 1$? Consider what goes wrong with $a = 2, n = 4$: compute $2^{\phi(4)} = 2^2 \bmod 4$ directly. The result is not $1$. The proof breaks because multiplication-by-$2$ does not permute the units of $\mathbb{Z}/4\mathbb{Z}$.

Try it

• Predict $\phi(15)$ before computing. Then enumerate the integers $1 \leq k \leq 15$ with $\gcd(k, 15) = 1$ and confirm.
• Use Euler’s theorem to compute $7^{40} \bmod 100$ without ever forming $7^{40}$. (Hint: $\phi(100) = 40$.)
• Compute $3^{30} \bmod 7$ via Fermat’s little theorem.
• Show that $\phi(p \cdot q) = (p - 1)(q - 1)$ when $p, q$ are distinct primes. (This is the formula RSA uses.)

A trap to watch for

The two formulas $\phi(p) = p - 1$ and $\phi(p^k) = p^k - p^{k-1}$ look similar but behave very differently. For a prime $p$, almost every residue is coprime — only $0$ is not. For a prime power $p^k$, the coprime residues miss every multiple of $p$, so the density of units drops to $(p-1)/p$. A common mistake is to assume $\phi(p^k) = p^k - 1$ by analogy — that would only be correct if $p^k$ were itself prime, which it isn’t for $k \geq 2$. Always factor first, then apply the totient formula prime-by-prime.

What you now know

You can compute $\phi(n)$ from the prime factorisation, apply Euler’s theorem to collapse huge powers into single residues, and recognise Fermat’s little theorem as the $n = p$ special case. In the final section, public-key cryptography, you will see how RSA stitches Euler’s theorem and the hardness of factoring into a working encryption scheme.

References

• Velleman, D. J. (2019). How to Prove It: A Structured Approach (3rd ed.). Cambridge University Press, §7.4.
• Hardy, G. H., Wright, E. M. (2008). An Introduction to the Theory of Numbers (6th ed.). Oxford University Press, ch. 5–6.
• Niven, I., Zuckerman, H. S., Montgomery, H. L. (1991). An Introduction to the Theory of Numbers (5th ed.). Wiley, ch. 2.
• Rosen, K. H. (2010). Elementary Number Theory (6th ed.). Pearson, ch. 6.
• Koblitz, N. (1994). A Course in Number Theory and Cryptography (2nd ed.). Springer, ch. 1.