Understanding Fermat's Little Theorem
Fermat's little theorem describes a remarkable relationship in modular arithmetic. For any prime number p and integer a not divisible by p, raising a to the power of (p−1) always produces a remainder of 1 when divided by p.
The theorem exists in two equivalent forms:
- General form: a^p ≡ a (mod p) for any integer a and prime p
- Simplified form: a^(p−1) ≡ 1 (mod p) when gcd(a, p) = 1
Pierre de Fermat discovered this principle in 1640 but never published a proof, claiming it would be too lengthy. Leonhard Euler later provided the first rigorous proof in 1736, though Leibniz had independently derived it decades earlier. Despite being named the "little" theorem (to distinguish it from Fermat's Last Conjecture), it remains one of number theory's most powerful and frequently applied results.
The Mathematical Statement
When p is prime and a shares no common factors with p, Fermat's little theorem gives us:
a^(p−1) ≡ 1 (mod p)
Alternatively: a^p ≡ a (mod p)
a— An integer coprime to p (gcd(a, p) = 1)p— A prime number greater than 1
Finding Multiplicative Inverses
One of the most practical applications of Fermat's little theorem is computing multiplicative inverses in modular arithmetic—essential for encryption algorithms and solving congruences.
If you need to find the multiplicative inverse of a modulo p (the number that satisfies a × x ≡ 1 (mod p)), Fermat's theorem provides an elegant shortcut. Since a^(p−1) ≡ 1 (mod p), we can rearrange this as:
a × a^(p−2) ≡ 1 (mod p)
This means a^(p−2) is the multiplicative inverse of a modulo p. You compute one modular exponentiation instead of running the extended Euclidean algorithm, making cryptographic operations significantly faster.
Primality Testing with Fermat's Test
Fermat's theorem naturally suggests a probabilistic primality test. The logic is simple: if a^(p−1) ≢ 1 (mod p) for some a coprime to p, then p is definitely composite.
The Fermat primality test works as follows:
- Choose a random integer a between 2 and p−2
- Compute a^(p−1) mod p
- If the result is not 1, p is composite (proven)
- If the result is 1, p might be prime; repeat with different values of a
After testing multiple random bases without finding a counterexample, you gain confidence that p is prime. However, Carmichael numbers (rare composites that fool Fermat's test for all coprime bases) mean this test is probabilistic rather than definitive. Modern cryptography uses more sophisticated tests like Miller–Rabin for certainty.
Critical Assumptions and Common Pitfalls
Fermat's little theorem only works under specific conditions; violating these assumptions leads to incorrect results.
- p must be prime — The theorem fails spectacularly for composite numbers. If you test p = 9 with a = 2, you get 2^8 ≡ 4 (mod 9), not 1. Always verify primality before applying the theorem, especially in cryptographic contexts where mistakes compromise security.
- a must be coprime to p — If a shares a factor with p (i.e., p divides a), the simplified form a^(p−1) ≡ 1 (mod p) breaks down. Use the general form a^p ≡ a (mod p) instead, or choose a different base. In primality testing, select a carefully to avoid accidentally picking a multiple of p.
- Carmichael numbers fool the test — Certain composite numbers like 561 = 3 × 11 × 17 satisfy a^(p−1) ≡ 1 (mod p) for all a coprime to p. Fermat's test alone cannot definitively prove primality; always combine it with additional tests or use deterministic algorithms for production systems.
- Modular exponentiation requires care — Computing a^(p−1) directly produces enormous intermediate values. Use fast modular exponentiation (repeated squaring) to keep numbers manageable and avoid overflow. Naive exponentiation makes even moderate inputs infeasible.