Fermat's Little Theorem: A Shortcut for Big Powers
Computing 3¹⁰⁰ mod 7 seems impossible. The number 3¹⁰⁰ has 48 digits.
But Fermat's Little Theorem says: 3⁶ ≡ 1 (mod 7).
So 3¹⁰⁰ = 3⁶ˣ¹⁶⁺⁴ = (3⁶)¹⁶ × 3⁴ ≡ 1¹⁶ × 81 ≡ 81 ≡ 4 (mod 7).
Done. Without computing 3¹⁰⁰.
Fermat's Little Theorem collapses huge powers into small remainders.
That's the unlock. The theorem says a^(p-1) ≡ 1 (mod p) for any prime p and any a not divisible by p. Powers of a cycle with period dividing p-1. Instead of computing a massive power, you reduce the exponent mod (p-1) and compute a tiny power.
The Theorem
Fermat's Little Theorem: If p is prime and gcd(a, p) = 1, then:
a^(p-1) ≡ 1 (mod p)
Equivalently, for any integer a:
aᵖ ≡ a (mod p)
Examples
p = 5, a = 2: 2⁴ = 16 ≡ 1 (mod 5) ✓
p = 7, a = 3: 3⁶ = 729 = 104 × 7 + 1 ≡ 1 (mod 7) ✓
p = 11, a = 2: 2¹⁰ = 1024 = 93 × 11 + 1 ≡ 1 (mod 11) ✓
Why It Works
Consider the set {a, 2a, 3a, ..., (p-1)a} mod p.
Claim: This set equals {1, 2, 3, ..., p-1} (in some order).
Why: If ia ≡ ja (mod p) for distinct i, j in {1, ..., p-1}, then (i-j)a ≡ 0 (mod p). Since gcd(a, p) = 1, we'd need p | (i-j). But |i-j| < p. Contradiction. So all residues are distinct.
So: 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, cancel (p-1)!:
a^(p-1) ≡ 1 (mod p) ∎
Computing Large Powers
To compute a^n mod p:
- Reduce the exponent: n ≡ r (mod p-1)
- Compute a^r mod p
Example: 5⁸⁷ mod 13
p = 13, so powers cycle with period 12. 87 = 7 × 12 + 3, so 87 ≡ 3 (mod 12). 5⁸⁷ ≡ 5³ = 125 ≡ 8 (mod 13).
The Order of an Element
The order of a mod p is the smallest positive k such that aᵏ ≡ 1 (mod p).
Fermat says the order divides p-1. It might be smaller.
p = 7:
- Order of 2: 2¹=2, 2²=4, 2³=1. Order is 3.
- Order of 3: 3¹=3, 3²=2, 3³=6, 3⁴=4, 3⁵=5, 3⁶=1. Order is 6.
3 has order p-1 = 6. Such elements are called primitive roots.
Finding Modular Inverses
From a^(p-1) ≡ 1, we get:
a × a^(p-2) ≡ 1 (mod p)
So a^(p-2) is the inverse of a mod p.
Example: Find 3⁻¹ mod 17.
3⁻¹ ≡ 3¹⁵ (mod 17)
Use fast exponentiation: 3² = 9 3⁴ = 81 ≡ 13 3⁸ ≡ 169 ≡ 16 ≡ -1 3¹⁵ = 3⁸ × 3⁴ × 3² × 3¹ ≡ (-1)(13)(9)(3) = -351 ≡ -351 + 21×17 = 6
Check: 3 × 6 = 18 ≡ 1 (mod 17) ✓
Euler's Generalization
Euler extended Fermat's theorem to composite moduli.
Euler's Theorem: If gcd(a, n) = 1, then:
a^φ(n) ≡ 1 (mod n)
where φ(n) is Euler's totient function: the count of integers from 1 to n that are coprime to n.
For prime p: φ(p) = p - 1, recovering Fermat.
For prime power pᵏ: φ(pᵏ) = pᵏ - pᵏ⁻¹.
For coprime m, n: φ(mn) = φ(m)φ(n).
The Totient Function
φ(1) = 1 φ(2) = 1 φ(6) = 2 (only 1 and 5 are coprime to 6) φ(12) = 4 (1, 5, 7, 11) φ(p) = p - 1 for prime p
Fermat Primality Test
To test if n is prime:
Pick random a with 1 < a < n. Compute a^(n-1) mod n.
If the result is not 1, n is definitely composite. If the result is 1, n is probably prime.
Caveat: Some composites (Carmichael numbers) pass for all a. The test is probabilistic.
Carmichael Numbers
561 = 3 × 11 × 17 is composite.
But for all a coprime to 561: a⁵⁶⁰ ≡ 1 (mod 561).
It passes Fermat's test for every base! These rare composites are Carmichael numbers.
To detect them, use stronger tests (Miller-Rabin).
Applications
Cryptography: RSA relies on Euler's theorem. Decryption works because m^(ed) ≡ m (mod n) when ed ≡ 1 (mod φ(n)).
Random number generators: Powers in finite fields have useful statistical properties.
Hashing: Fermat's theorem helps analyze hash function behavior.
The Core Insight
Fermat's Little Theorem says: powers cycle mod p.
a^(p-1) returns to 1, so aᵖ = a, aᵖ⁺¹ = a², and so on. The cycle length (order) divides p-1.
This cycling is why huge exponents become manageable. It's why modular inverses are easy to find. It's why RSA works.
The theorem connects the multiplicative structure of ℤ/pℤ to the simpler structure of remainders. Primes make this structure especially clean.
Part 9 of the Number Theory series.
Previous: Congruences: When Different Numbers Are the Same Next: Cryptography: Number Theory Protects Your Secrets
Comments ()