Fermat's Little Theorem

We now meet the first of the great theorems of modular arithmetic — small to state, vast in consequence. It describes what happens when you raise a number to a prime-related power and look at the remainder. The pattern is astonishingly clean, and it powers primality testing and public-key cryptography alike.

The statement

Let p be prime. Then for every integer a:

if p \nmid a, then a^{p-1} \equiv 1 \pmod{p};
for any a, a^{p} \equiv a \pmod{p}.

Test it with p = 5, a = 2: 2^{4} = 16 \equiv 1 \pmod 5. And 3^{5} = 243 \equiv 3 \pmod 5. Both forms hold.

Why it's true: shuffling the residues

Here is the elegant argument. Take the nonzero residues 1, 2, \dots, p-1 and multiply every one by a (with p \nmid a). Because a is invertible, this just permutes them — you get the same set back in a different order. So their products match modulo p:

(a\cdot 1)(a \cdot 2)\cdots(a(p-1)) \equiv 1 \cdot 2 \cdots (p-1) \pmod p.

The left side is a^{p-1}(p-1)!. Cancelling the common (p-1)! (every factor is coprime to p, so it cancels) leaves a^{p-1} \equiv 1 \pmod p.

What it gives us

Fermat's theorem is a power-reducer: exponents can be taken modulo p - 1. To find 2^{100} \bmod 7, note 2^{6} \equiv 1, and 100 = 6\cdot 16 + 4, so 2^{100} \equiv 2^{4} = 16 \equiv 2 \pmod 7. It also hands us inverses for free — a^{-1} \equiv a^{p-2} \pmod p — and it generalises, beyond primes, to Euler's theorem.