Fermat's Little Theorem
For a prime p, a^p ≡ a (mod p) for every integer a — a congruence that underlies fast primality testing.
Fermat's Little Theorem
Fermat's little theorem states that if p is a prime, then for every integer a,
and, when a is not a multiple of p, the sharper form
It is "little" only by contrast with Fermat's Last Theorem. In practice it is enormous: this single congruence is the foundation of nearly every fast primality test and a load-bearing beam under RSA.
What it says, concretely
Take p = 7 and a = 3. Then 3^{6} = 729 = 104\cdot 7 + 1, so 3^{6}\equiv 1\pmod 7. Try any base coprime to 7 and the same thing happens — raising it to the 6th power lands back on 1. The theorem promises this is no coincidence: in arithmetic mod a prime, the powers of any nonzero base cycle through a length that always divides p - 1.
Here 3 is a primitive root mod 7: its powers visit all six nonzero residues before closing the loop. Not every base does — but every base's cycle length divides p-1, which is exactly why a^{p-1}\equiv 1.
Why it is true
There is a one-line combinatorial proof. Consider the nonzero residues \{1, 2, \dots, p-1\} and multiply each by a (with \gcd(a,p)=1). Because multiplication by a is invertible mod p, this just permutes the same set. So the two products are equal:
The left side is a^{p-1}\,(p-1)! and the right is (p-1)!. Since (p-1)! is coprime to p, cancel it to get a^{p-1}\equiv 1. It is a special case of Euler's theorem (Euler's Totient Function), which replaces p-1 by \varphi(n) for any modulus n.
The catch: Carmichael numbers
The Fermat test has a flaw. A few rare composites masquerade as primes by passing it for every base coprime to them. The smallest is 561 = 3\cdot 11\cdot 17: it is composite, yet a^{560}\equiv 1 \pmod{561} for all a coprime to 561. These are the Carmichael numbers, and they are why robust testing uses the stronger Miller–Rabin refinement rather than Fermat's theorem alone.