Fermat's Little Theorem
Reference for Fermat's Little Theorem: a^(p-1) ≡ 1 (mod p) when p is prime and gcd(a, p) = 1.
Foundation of RSA and modular exponentiation.
The Theorem
For any prime number p and any integer a not divisible by p, raising a to the power (p − 1) and reducing modulo p always gives 1.
Alternate Form
This version holds for any integer a (no coprimality requirement). It is equivalent to the first form when a is not divisible by p, and is trivially true when a is.
Variables
| Symbol | Meaning | Constraint |
|---|---|---|
| p | A prime number | p prime |
| a | An integer | For form 1: gcd(a, p) = 1 |
| ≡ (mod p) | Congruence modulo p | Same remainder when divided by p |
Example — Verifying with p = 7
Verify Fermat's Little Theorem for a = 3 and p = 7.
a^(p − 1) = 3^6 = 729
729 mod 7 = ?
7 × 104 = 728, so 729 = 7 × 104 + 1
3^6 ≡ 1 (mod 7) ✓
Example — Computing Large Powers
Compute 5^100 mod 11 without doing 5^100 directly.
By Fermat: 5^10 ≡ 1 (mod 11)
100 = 10 × 10, so 5^100 = (5^10)^10
(5^10)^10 ≡ 1^10 ≡ 1 (mod 11)
5^100 mod 11 = 1
This is the core of efficient modular exponentiation — reducing exponents modulo p − 1 first, then computing the smaller power.
Computing Modular Inverses
Fermat's Little Theorem gives a direct formula for modular inverse: since a × a^(p−2) = a^(p−1) ≡ 1 (mod p), it follows that a^(p−2) is the modular inverse of a mod p.
Example — Modular Inverse
Find the inverse of 3 modulo 11.
3⁻¹ ≡ 3^(11 − 2) = 3^9 (mod 11)
3² = 9, 3⁴ = 81 = 11 × 7 + 4, so 3⁴ ≡ 4
3⁸ ≡ 4² = 16 ≡ 5 (mod 11)
3⁹ = 3⁸ × 3 ≡ 5 × 3 = 15 ≡ 4 (mod 11)
3⁻¹ ≡ 4 (mod 11). Verify: 3 × 4 = 12 ≡ 1 ✓
Why It Matters for Cryptography
Fermat's Little Theorem (along with its generalization, Euler's theorem) is foundational to RSA encryption. RSA works because the encryption and decryption exponents e and d satisfy e × d ≡ 1 (mod (p − 1)(q − 1)) where p and q are large primes. The proof that decryption recovers the original message relies directly on Fermat's Little Theorem applied to messages modulo p and q.
Primality Testing
If a^(n − 1) ≢ 1 (mod n) for some a coprime to n, then n is definitely composite. This gives a fast primality test (the Fermat test). However, the converse fails: some composite numbers (Carmichael numbers like 561 = 3 × 11 × 17) satisfy Fermat's congruence for every a coprime to them. Better tests like Miller-Rabin extend the idea to handle these false positives.
When to Use It
- Computing large modular powers efficiently (reduce the exponent mod p − 1 first)
- Finding modular multiplicative inverses (a⁻¹ = a^(p − 2) when p is prime)
- Implementing RSA encryption and decryption operations
- Quick primality screening before more expensive tests
- Proving identities in number theory and combinatorics
Generalization
Euler's theorem generalizes Fermat's: a^φ(n) ≡ 1 (mod n) for any n and any a coprime to n, where φ(n) is Euler's totient. When n is prime, φ(n) = n − 1 and we recover Fermat's Little Theorem.