Fermat's Little Theorem

The statement

Fermat's little theorem says: if p is a prime number and a is an integer not divisible by p, then a^(p − 1) ≡ 1 (mod p).

An equivalent form drops the coprime requirement: a^p ≡ a (mod p) for every integer a. The two forms agree when gcd(a, p) = 1, since dividing both sides of a^p ≡ a by a gives a^(p − 1) ≡ 1. When p divides a, both sides of a^p ≡ a reduce to 0 mod p, which is also true.

The theorem first appeared in a letter Fermat sent to Frénicle de Bessy in October 1640 — almost a quarter-millennium before the rigorous abstract-algebra framework that explains it. Fermat asserted the result without full proof; Leibniz gave the first written proof around 1683, and Euler published a clean version in 1736.

The proof — pigeonhole on residues

The slickest proof goes like this. Consider the (p − 1) numbers a, 2a, 3a, ..., (p − 1)a. None is divisible by p (each is a non-zero a times a non-zero integer less than p, and p is prime). Reduce them mod p; the claim is that this set equals {1, 2, ..., p − 1} in some order.

To see why, suppose i·a ≡ j·a (mod p) with 1 ≤ i, j ≤ p − 1. Then (i − j)·a ≡ 0 (mod p). Since p is prime and gcd(a, p) = 1, p must divide (i − j), forcing i ≡ j (mod p). With both in [1, p − 1], that means i = j. So the (p − 1) products are pairwise distinct mod p — they are a permutation of (1, 2, ..., p − 1).

Multiply them all together:

(a)(2a)(3a)...((p−1)a) ≡ (1)(2)(3)...(p−1) (mod p)
a^(p−1) · (p−1)! ≡ (p−1)! (mod p)

Since gcd((p − 1)!, p) = 1 (none of 1, 2, ..., p − 1 share a factor with prime p), we can cancel (p − 1)! from both sides:

a^(p−1) ≡ 1 (mod p)

Done. The same argument works in any finite group via Lagrange's theorem: the order of any element divides the order of the group, and (ℤ/p)* has order p − 1.

Worked example: 7^222 mod 11

How would you compute 7²²² mod 11 by hand? Direct repeated multiplication would need 221 multiplications; even with binary exponentiation, ~16 squarings and reductions. Fermat's theorem cuts to the answer in two lines.

Since 11 is prime and gcd(7, 11) = 1, Fermat's theorem says 7¹⁰ ≡ 1 (mod 11). Reduce the exponent 222 mod 10:

222 = 22 × 10 + 2
222 mod 10 = 2

So 7^222 = 7^(22 × 10 + 2)
        = (7^10)^22 · 7^2
        ≡ 1^22 · 49
        ≡ 49 (mod 11)
        ≡ 49 − 44
        ≡ 5 (mod 11)

Verification: 7¹ = 7, 7² = 49 ≡ 5, 7³ ≡ 35 ≡ 2, 7⁴ ≡ 14 ≡ 3, 7⁵ ≡ 21 ≡ 10, 7⁶ ≡ 70 ≡ 4, 7⁷ ≡ 28 ≡ 6, 7⁸ ≡ 42 ≡ 9, 7⁹ ≡ 63 ≡ 8, 7¹⁰ ≡ 56 ≡ 1 ✓. The cycle has period 10 (the multiplicative order of 7 mod 11 is exactly p − 1 here, so 7 is a primitive root mod 11).

Same trick scales: 17^(10^6) mod 31 = 17^((10^6) mod 30) mod 31 = 17^(10^6 mod 30) = 17^(10) (since 10^6 ≡ 10 mod 30) = ... a single 10th-power computation instead of a million.

The Fermat primality test

Reverse the implication: if a^(n − 1) ≢ 1 (mod n) for any base a coprime to n, then n cannot be prime. This gives a polynomial-time compositeness test:

1. Pick a random base a in [2, n − 2].
2. Compute a^(n − 1) mod n by fast exponentiation (O(log n) multiplications).
3. If the result isn't 1, output COMPOSITE.
4. If the result is 1, output PROBABLY PRIME (or repeat with another base).

For most composites, almost any base a yields a^(n − 1) ≢ 1 (mod n), so a few rounds catch them quickly. The cost: O(log³ n) bit operations per round for n up to a few thousand bits.

The catch is Carmichael numbers — composites that pass the Fermat test for every coprime base. Miller-Rabin patches this by also examining the square roots of 1 mod n; in any group, there are exactly two square roots of 1 (namely ±1) when n is prime, but composites have extra "non-trivial" square roots that the test detects.

Carmichael numbers — the dangerous pseudoprimes

A Carmichael number is a composite n for which a^(n − 1) ≡ 1 (mod n) holds for every a coprime to n. These are the composites that the Fermat test never rules out, no matter how many bases you try (the only failures come from bases sharing a factor with n, which a coincidental gcd check would catch).

The first ten Carmichael numbers are:

561 = 3 × 11 × 17
1105 = 5 × 13 × 17
1729 = 7 × 13 × 19   (Ramanujan's taxicab number)
2465 = 5 × 17 × 29
2821 = 7 × 13 × 31
6601 = 7 × 23 × 41
8911 = 7 × 19 × 67
10585 = 5 × 29 × 73
15841 = 7 × 31 × 73
29341 = 13 × 37 × 61

Korselt's criterion (1899) characterises them: n is Carmichael iff n is squarefree and (p − 1) divides (n − 1) for every prime divisor p of n. Alford, Granville and Pomerance proved in 1994 that there are infinitely many Carmichael numbers, settling a long-open conjecture. The bound is roughly: there are at least n^(1/3) Carmichael numbers below n for n large enough.

Fermat's little theorem and its relatives

Theorem	Modulus	Coprime requirement	Statement	Application
Fermat's little theorem	Prime p	gcd(a, p) = 1	a^(p−1) ≡ 1 (mod p)	Fast modular exponent reduction
Euler's theorem	Any n > 0	gcd(a, n) = 1	a^φ(n) ≡ 1 (mod n)	RSA decryption
Carmichael's theorem	Any n > 0	gcd(a, n) = 1	a^λ(n) ≡ 1 (mod n)	Tighter than Euler's bound
Wilson's theorem	Prime p	None	(p−1)! ≡ −1 (mod p)	Theoretical, not practical primality test
Miller-Rabin test	Odd n > 2	gcd(a, n) = 1	Examines square roots of 1	Probabilistic primality (1/4 error per round)
Lucas-Lehmer test	Mersenne 2^p − 1	Specialised	Sequence ≡ 0 (mod 2^p − 1)	Largest known primes (GIMPS)
AKS primality test	Any n > 1	None	Polynomial identity	Provable primality, deterministic, polynomial-time

Fermat's little theorem occupies the bottom rung — it is the simplest and most widely applicable. Each subsequent theorem either weakens an assumption (Euler removes the prime requirement) or strengthens the conclusion (Miller-Rabin catches Carmichael numbers).

Where Fermat's little theorem shows up

• RSA primality generation. Generating a 2048-bit RSA prime requires testing roughly 1500 candidates. Each candidate is filtered with a Fermat-style test (or Miller-Rabin, which subsumes it) to reject composites in under a millisecond. Without Fermat's theorem, every "is this prime?" check would require trial division up to √n ≈ 2¹⁰²⁴, which is computationally hopeless.
• RSA decryption — exponent reduction. RSA private keys with modulus n = pq use the relation e · d ≡ 1 (mod (p − 1)(q − 1)). Fermat's theorem says a^(p−1) ≡ 1 (mod p), so a^e^d = a^(1 + k(p−1)(q−1)) ≡ a (mod n) — the reason RSA decryption recovers the message.
• Diffie-Hellman key exchange. The shared secret g^(ab) mod p requires raising a generator g to a private exponent. Fermat's theorem bounds the multiplicative order of g by p − 1, so all key material lies within a finite cyclic subgroup. Real-world TLS uses primes p with (p − 1)/2 also prime, ensuring the subgroup orders are well-known.
• Probabilistic compositeness sieves. Cryptographic libraries like OpenSSL, BoringSSL and the Crypto++ collection apply 32 to 50 Miller-Rabin rounds per prime candidate. Each round leverages Fermat's congruence as the underlying check; the 1/4-per-round error gives < 2^(−100) failure probability after 50 rounds.
• Hash-based digital signatures. The Merkle-Damgård construction and modern hash-based signatures (XMSS, SPHINCS+) often use Fermat-style identities in their internal block functions. Even when the cryptographic primitive isn't directly modular exponentiation, the structural reasoning about cyclic groups traces back to Fermat's theorem.

Variants and extensions

• Euler's theorem. a^φ(n) ≡ 1 (mod n) whenever gcd(a, n) = 1. Specialises to Fermat's theorem when n is prime (φ(p) = p − 1). The full RSA framework requires Euler's theorem on composite moduli, not Fermat's on prime moduli.
• Carmichael function λ(n). The smallest exponent k such that a^k ≡ 1 (mod n) for all coprime a. Always divides φ(n), and gives the tightest universal bound. λ(n) = lcm{p^(a−1)(p − 1) : p^a || n} (for odd primes; with adjustments for 2^a).
• Lucas's theorem. A binomial-coefficient version: C(n, k) mod p can be computed by writing n and k in base p and multiplying digit-by-digit binomial coefficients. Used to compute large binomials mod small primes.
• Hensel's lemma. Lifts a Fermat-style congruence from mod p to mod p^k. Critical for solving polynomial equations modulo prime powers and for the structure theory of p-adic numbers.
• Pseudo-random generators. Blum-Blum-Shub generates pseudo-random bits by squaring modulo n = pq. The Fermat–Euler structure guarantees the period is at most λ(λ(n)) — provable cryptographic strength rests on Fermat's theorem.

Common pitfalls

• Forgetting the coprime condition. a^(p − 1) ≡ 1 (mod p) requires gcd(a, p) = 1. When p divides a, the result is 0, not 1. The "for any a" form, a^p ≡ a (mod p), avoids this trap by allowing both cases.
• Confusing Fermat's little theorem with Fermat's last theorem. The "last" theorem (no integer solutions to xⁿ + yⁿ = zⁿ for n ≥ 3) is unrelated to the "little" theorem. Wiles proved the last theorem in 1995; the little theorem has been proven in dozens of ways since the 1680s.
• Using Fermat as a proof of primality. a^(n − 1) ≡ 1 (mod n) does NOT prove that n is prime. Carmichael numbers like 561 satisfy the congruence for every coprime base. Use Miller-Rabin or AKS for actual primality proofs.
• Reducing exponents mod p instead of mod (p − 1). When computing a^N mod p with gcd(a, p) = 1, reduce N mod (p − 1), NOT mod p. The order of (ℤ/p)* is p − 1, not p. This is the most common student error in RSA derivations.
• Assuming the result mod p^k. Fermat's theorem gives a^(p − 1) ≡ 1 (mod p), not (mod p²) or higher. To raise to higher prime powers, use Hensel lifting or Euler's theorem with φ(p^k) = p^(k − 1)(p − 1).