Euler's Theorem

Pick a number n. Pick another number a that shares no common factor with n. Now raise a to a very specific power — the totient \varphi(n) — and reduce the result modulo n. No matter which coprime a and n you chose, you land on exactly the same number every single time: 1. It's a guaranteed "return to start," and Euler discovered it by generalising a special case that Fermat had only proved for prime moduli.

This isn't just a curiosity. It is the exact mathematical guarantee that makes RSA decryption actually recover the message you encrypted — every secure web page you have ever loaded leaned on this theorem, whether or not the browser told you so.

The statement

If \gcd(a, n) = 1, then

a^{\varphi(n)} \equiv 1 \pmod{n}.

When n = p is prime, \varphi(p) = p-1 and this collapses back to Fermat's Little Theorem — Euler's version is the strictly more general statement, valid for every modulus, prime or not.

Worked example: watch it return to 1

Take a = 2 and n = 9. First, \gcd(2, 9) = 1, so the theorem applies. From the totient page, \varphi(9) = 6 (the numbers 1,2,4,5,7,8 are coprime to 9). The theorem promises 2^{6} \equiv 1 \pmod 9. Check it by building up the powers of 2, reducing mod 9 at every step so the numbers stay small:

2^1{=}2,\ \ 2^2{=}4,\ \ 2^3{=}8,\ \ 2^4{\equiv}7,\ \ 2^5{\equiv}5,\ \ 2^6{\equiv}1 \pmod 9. \checkmark

Right on schedule, the sixth power lands exactly on 1 — not before, not after. Watch the same cycle in the chart: the sequence climbs, wraps, and always crosses back through 1 the moment the exponent hits a multiple of \varphi(9) = 6.

A subtlety worth flagging: Euler's theorem guarantees a return to 1 by exponent \varphi(n), but doesn't promise that's the first time it happens. Try a = 2, n = 7 (prime, so \varphi(7) = 6): 2^1{=}2,\ 2^2{=}4,\ 2^3{\equiv}1 \pmod 7 — it already hits 1 at step 3, a proper divisor of 6. The exponent \varphi(9)=6 was the exact first return for 2 mod 9 above, but that's not guaranteed in general — only that some multiple of the true first-return step divides \varphi(n), so raising to the \varphi(n)-th power always lands safely on 1, sooner or not.

Why it's true

The same shuffling argument as Fermat's, but over the right set. Let u_1, \dots, u_{\varphi(n)} be the residues coprime to n. Multiplying them all by a (itself coprime to n) permutes the set, so the products agree:

a^{\varphi(n)} \, u_1 u_2 \cdots u_{\varphi(n)} \equiv u_1 u_2 \cdots u_{\varphi(n)} \pmod n.

Each u_i is invertible, so cancel the product and a^{\varphi(n)} \equiv 1 remains.

Euler's theorem next to Fermat's

Laid side by side, the family resemblance — and the one real difference — is easy to see:

Swap in n = p: since a prime's only numbers below it are all coprime to it, \varphi(p) = p - 1 and Euler's statement becomes Fermat's word for word. Fermat's theorem never went away — it's simply the prime-modulus slice of the bigger picture Euler carved out a century later.

Every version of this theorem carries the same fine print: \gcd(a, n) = 1 is not optional decoration, it's load-bearing. Drop it, and the guarantee evaporates.

Try a = 3 and n = 9 — the same modulus as above, but this time \gcd(3, 9) = 3 \ne 1, so the condition fails. Does 3^{\varphi(9)} = 3^{6} still land on 1 mod 9? Compute it: 3^6 = 729 = 81 \times 9, so 3^{6} \equiv 0 \pmod 9 — nowhere near 1. The theorem simply doesn't promise anything once a and n share a factor; always check \gcd(a,n) = 1 before reaching for this result, not after.

Rule of thumb: before writing a^{\varphi(n)} \equiv 1, say the coprimality check out loud — "is \gcd(a,n) equal to 1?" If you can't answer yes immediately, compute the \gcd first. It takes seconds and saves you from confidently quoting a theorem that has quietly stopped applying.

How RSA uses it

RSA picks n = pq and an encryption exponent e, then finds d with ed \equiv 1 \pmod{\varphi(n)}. Encryption is c = m^{e} and decryption c^{d} = m^{ed}. Because ed = 1 + k\varphi(n), Euler's theorem makes the round trip return the message:

m^{ed} = m^{1 + k\varphi(n)} = m \cdot \left(m^{\varphi(n)}\right)^{k} \equiv m \cdot 1^{k} = m \pmod n.

That middle step — m^{\varphi(n)} \equiv 1 — is exactly Euler's theorem doing the work, silently, every single time someone decrypts an RSA message. (Strictly, RSA needs \gcd(m,n)=1 for this argument; the rare exceptional messages that share a factor with n can be handled separately and don't threaten the scheme in practice.) The whole security rests on the fact, from the totient page, that finding d needs \varphi(n), which needs the factors of n.

A toy-sized run-through, small enough to check by hand. Pick primes p = 3, q = 11, so n = 33 and \varphi(n) = 2 \times 10 = 20. Choose encryption exponent e = 3 (coprime to 20), and solve 3d \equiv 1 \pmod{20} to get d = 7 (check: 3 \times 7 = 21 \equiv 1 \pmod{20}). Encrypt the message m = 4:

c = 4^{3} \bmod 33 = 64 \bmod 33 = 31.

Now decrypt, raising the ciphertext to d = 7:

c^{7} \bmod 33 = 31^{7} \bmod 33 = 4 = m. \checkmark

The message comes back out exactly — because ed = 21 = 1 + 1 \cdot \varphi(33), Euler's theorem is precisely what forces that final 31^{7} to collapse back down to 4 rather than landing anywhere else.

Euler proved this theorem in 1763, generalising Fermat's prime-only special case from a century earlier. He had no notion of computers, let alone networks — he was simply chasing a beautiful pattern in modular arithmetic for its own sake, the way mathematicians of his era often did.

It sat as an elegant piece of pure mathematics for roughly two centuries. Then in 1977, Rivest, Shamir, and Adleman needed exactly this guarantee to make their new encryption scheme actually decrypt back to the original message, and Euler's theorem was waiting, fully formed, ready to become the mathematical engine inside every RSA-protected connection on the modern internet. Few purely theoretical results have ever had such a long fuse — or such an enormous payoff once it went off.

Multiply that out: billions of devices perform RSA-style operations every single day — loading websites, verifying software updates, signing into banking apps — and every one of them is quietly relying on the exact same guarantee Euler wrote down for its own sake, centuries before there was anything electronic to protect.