Proofs of Fermat's Little Theorem

Number Theory · Axiom Academy

LESSON Proofs of Fermat's Little Theorem Exploring multiple proof techniques for one of number theory's fundamental results 1. The Theorem and Combinatorial Approach We begin with the statement of Fermat's Little Theorem and introduce a beautiful combinatorial proof using necklace counting. Proof idea: Consider necklaces with p beads, each colored in one of a colors. We'll count them two ways: Total colorings: a p (each bead has a color choices) Solid-color necklaces: a (all beads the same color) The remaining ( a p - a ) necklaces can be grouped into equivalence classes of size p under rotation 2. Completing the Necklace Proof We demonstrate how rotations create equivalence classes of size exactly p for non-monochromatic necklaces. Key observation: For a necklace that isn't solid-colored, all p rotations produce distinct patterns (because p is prime). If any two rotations were the same, the pattern would repeat with period dividing p , which must be 1 or p . Non-monochromatic necklaces: a p - a These form groups of size p , so p divides ( a p - a ) A more algebraic approach uses the structure of the multiplicative group of integers modulo p . The set 1, 2, 3, ..., p -1 forms a group under multiplication mod p This group has exactly p -1 elements For any element a in this group, by Lagrange's theorem, a p-1 = 1 Visualization: We'll show how multiplying by a permutes the elements 1, 2, ..., p -1 , and taking this to the ( p -1)th power returns to the identity.

This is the written version of the interactive lesson above. See the full Number Theory course.