Proof of Fermat's Little Theorem
You'll learn a beautiful proof showing why a^(p-1) ≡ 1 (mod p) for any prime p and integer a not divisible by p.
The Core Idea
Fermat's Little Theorem states that if p is prime and a is not divisible by p, then a^(p-1) ≡ 1 (mod p). The proof hinges on a clever observation: when you multiply the numbers {1, 2, 3, ..., p-1} by a, you simply rearrange them modulo p—you get the same set, just scrambled.
The Proof
Consider the set of non-zero residues: {1, 2, 3, ..., p-1}.
Now multiply each element by a: {a, 2a, 3a, ..., (p-1)a}.
Claim: These are just a permutation of {1, 2, ..., p-1} modulo p.
Why?
- None equals 0 (mod p), since
aisn't divisible bypand neither are 1 through p-1 - No two are equal: if
ia ≡ ja (mod p)with i ≠ j, we could cancela(using modular inverses), gettingi ≡ j (mod p)—impossible for distinct values in our range
Since both sets contain the same p-1 elements modulo p, their products must be equal:
a · 2a · 3a · ... · (p-1)a ≡ 1 · 2 · 3 · ... · (p-1) (mod p)
Simplify the left side:
a^(p-1) · (1 · 2 · 3 · ... · (p-1)) ≡ (1 · 2 · 3 · ... · (p-1)) (mod p)
Since (p-1)! is not divisible by p, we can divide both sides by it:
a^(p-1) ≡ 1 (mod p)
Key Takeaway: Fermat's Little Theorem follows from the fact that multiplying {1, 2, ..., p-1} by any a coprime to p merely permutes the set modulo p, allowing us to compare products and cancel to reveal a^(p-1) ≡ 1 (mod p).