Number Theory
Fermat's Little Theorem – A Cornerstone of Number Theory
Fermat's Little Theorem states that if p is a prime number and a is any integer not divisible by p, then ap−1 ≡ 1 (mod p). Despite its modest name (chosen to distinguish it from Fermat's much more famous Last Theorem), it is one of the most useful results in all of number theory, turning impossibly large powers into small, manageable calculations.
Pierre de Fermat stated the theorem in a 1640 letter to his fellow mathematician Bernard Frénicle de Bessy – without providing a proof, as was Fermat's habit throughout his life (a pattern that earned him the nickname the “Prince of Amateurs”). The first proof came from Gottfried Wilhelm Leibniz around 1683, in an unpublished manuscript, and the theorem was proved again independently and published by Leonhard Euler in 1736. Euler did not stop there: in 1763 he generalised the result so that it works for any modulus, not just primes – a result now called Euler's theorem, the subject of the next page.
The Theorem
For prime p and gcd(a, p) = 1: ap−1 ≡ 1 (mod p)
Equivalently, for every integer a: ap ≡ a (mod p)
36 = 729.
729 ÷ 7 = 104 remainder 1, so 729 mod 7 = 1. ✓
Using It to Simplify Huge Powers
Because ap−1 ≡ 1 (mod p), any exponent can first be reduced modulo (p−1) before computing – turning an enormous power into a tiny one.
11 is prime, so 510 ≡ 1 (mod 11). Reduce the exponent: 37 mod 10 = 7.
So 537 ≡ 57 (mod 11). Computing 57 mod 11 gives 3.
The Fermat Primality Test – and Its Limits
Since am−1 ≡ 1 (mod m) should hold whenever m is prime, testing this for a random witness a gives a quick (but not perfect) way to check whether a large number m might be prime. The catch: a small family of composite numbers, called Carmichael numbers (the smallest is 561 = 3 × 11 × 17, discovered by Robert Carmichael in 1910), pass this test for every valid witness a despite not being prime at all. This is why modern software uses stronger tests, such as the Miller–Rabin test, rather than relying on Fermat's test alone.
Key Takeaways
- For prime p and gcd(a, p) = 1: ap−1 ≡ 1 (mod p).
- Reducing the exponent modulo (p−1) makes huge powers easy to compute.
- The theorem gives a fast (if imperfect) primality test, fooled only by rare Carmichael numbers.
- Euler generalised the theorem in 1763 to work with any modulus, not only primes.