Fermat's Little Theorem

Discrete Math · Axiom Academy

LESSON Fermat's Little Theorem A fundamental result in number theory: for prime p and any integer a not divisible by p, a p-1 ≡ 1 (mod p). Proven through an elegant counting argument with necklaces. Equivalently, for any integer a and prime p: a p ≡ a (mod p) Consider making necklaces using p beads, where each bead can be one of a different colors. We'll count these necklaces in two different ways to prove the theorem. Counting method 1: There are a p total strings of length p using a colors (before considering rotations). Counting method 2: Each necklace corresponds to exactly p rotations, except for the a single-color necklaces which look the same under all rotations. From our necklace counting, we can establish that the number of distinct necklaces is: 4. Application: Primality Testing Fermat's Little Theorem gives us a way to test if a number might be prime. If n is prime and gcd(a, n) = 1, then a n-1 ≡ 1 (mod n). The contrapositive is useful: 5. Finding Multiplicative Order The multiplicative order of a modulo p is the smallest positive integer k such that a k ≡ 1 (mod p). Fermat's Little Theorem tells us this order divides p - 1. We know the order divides p - 1 (by Fermat's Little Theorem) Check divisors of p - 1 in increasing order The first d where a d ≡ 1 (mod p) is the multiplicative order 6. Connection to Euler's Theorem Fermat's Little Theorem is a special case of the more general Euler's Theorem, which works for any modulus n (not just primes).

This is the written version of the interactive lesson above. See the full Discrete Math course.