What is Euler's Theorem, and how does it generalize Fermat's Little Theorem?

Euler's Theorem states: if $\gcd(a, n) = 1$, then $a^{\varphi(n)} \equiv 1 \mod n$. It works for ANY modulus n, not just primes — making it the foundation of RSA.

* Euler's theorem holds for any modulus n; Fermat's little theorem is the special case where n is prime, since then φ(p) = p−1. Both also hand you the modular inverse. *

The theorem: For any $n$ and $\gcd(a, n) = 1$: $$a^{\varphi(n)} \equiv 1 \mod n$$

Equivalent forms:

• $a^{\varphi(n)+1} \equiv a \mod n$
• $a^{\varphi(n)-1} \equiv a^{-1} \mod n$ (gives the inverse!)

How it generalizes Fermat:

• Fermat: $a^{p-1} \equiv 1 \mod p$ (only for prime $p$)
• Euler: $a^{\varphi(n)} \equiv 1 \mod n$ (for any $n$)
• When $n = p$ (prime): $\varphi(p) = p - 1$, so Euler reduces to Fermat

Example: $a = 4$, $n = 9$, $\varphi(9) = 6$:

• $4^6 \equiv 1 \mod 9$ ✓
• $4^7 \equiv 4 \mod 9$ ✓
• $4^5 \equiv 7 \equiv 4^{-1} \mod 9$. Check: $7 \cdot 4 = 28 \equiv 1 \mod 9$ ✓

For RSA: With $N = p \cdot q$: $a^{\varphi(N)} = a^{(p-1)(q-1)} \equiv 1 \mod N$. This is directly used to construct the RSA decryption exponent.

Go deeper:

• Euler's theorem (Wikipedia) — the generalization that underpins RSA decryption.
• Übungen zum Satz von Euler (German) — guided exercises applying Euler's theorem.