Proving Fermat's Little Theorem

Intro to Proofs · Axiom Academy

EXAMPLE Proving Fermat's Little Theorem The classic counting proof: multiplying by a just shuffles the nonzero residues mod p . Let p be a prime and let a be an integer with . Prove Fermat's Little Theorem : . The key idea, for p = 5 , a = 2 Multiplying each nonzero residue by a = 2 and reducing mod 5 sends to — the same four numbers, just reordered. That bijection is the whole engine of the proof. Nicely done. You proved Fermat's Little Theorem with the classic "multiply and cancel" counting argument. The moving parts: Multiplication permutes the residues: when , the map is a bijection of onto itself. Same set, same product: so , i.e. . Cancellation needs coprimality: none of is divisible by the prime p , so and we may cancel (p-1)! . The result: . Multiplying through by a recovers the companion form , which holds for every integer a . This theorem underpins modular exponentiation, RSA encryption, and fast primality tests — a small counting trick with an outsized reach.

This is the written version of the interactive lesson above. See the full Intro to Proofs course.