Euler's Theorem
Fermat's Little Theorem
needs a prime modulus. Euler freed it from that restriction, replacing the exponent
p - 1 with the
totient
\varphi(n). The result works for any modulus — and it is the
exact statement that makes RSA decryption work.
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. Check it with a = 3,
n = 10: \varphi(10) = 4, and
3^{4} = 81 \equiv 1 \pmod{10}.
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.
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.
The whole security rests on the fact, from the
totient page,
that finding d needs \varphi(n), which needs
the factors of n.