Fermat's Little Theorem
Fermat's little theorem: if p is prime and gcd(a,p)=1, then a^(p-1) is congruent to 1 mod p.
The foundation of RSA encryption and primality testing.
The Formula
a^(p−1) ≡ 1 (mod p) (p prime, gcd(a,p) = 1)
Pierre de Fermat stated this theorem in 1640 (without proof). Leonhard Euler proved it in 1736. It is one of the most useful results in number theory and forms the mathematical core of RSA public-key encryption — the algorithm that secures most internet communications today.
Variables
| Symbol | Meaning |
|---|---|
| a | Any integer |
| p | A prime number |
| ≡ | Congruent modulo (same remainder after division) |
| gcd(a, p) = 1 | a and p share no common factors (coprime); automatic when p is prime and p does not divide a |
Example 1 — Computing Large Powers
Calculate 2^100 mod 101. (Note: 101 is prime.)
By Fermat's little theorem: 2^(101−1) = 2^100 ≡ 1 (mod 101)
2^100 mod 101 = 1. No need to compute 2^100 (a 31-digit number) at all!
Example 2 — Reducing Larger Exponents
Calculate 3^1000 mod 7. (7 is prime, so 3^6 ≡ 1 mod 7.)
1000 = 6 × 166 + 4, so 3^1000 = (3^6)^166 × 3^4
(3^6)^166 ≡ 1^166 = 1 (mod 7)
3^4 = 81 = 11 × 7 + 4
3^1000 ≡ 1 × 4 = 4 (mod 7)
When to Use It
Fermat's little theorem is used when:
- RSA encryption: The decryption formula relies on Euler's theorem (the generalization of Fermat's theorem). For primes p and q, the RSA modulus n = pq, and messages are encrypted and decrypted using modular exponentiation.
- Primality testing: If a^(p−1) mod p ≠ 1 for some a, then p is definitely composite. This is the Fermat primality test. The Miller-Rabin test extends this idea.
- Fast modular exponentiation: Reducing exponents modulo (p−1) before computing, using repeated squaring.
- Modular inverse: a^(p−2) ≡ a^(−1) (mod p) when p is prime — gives the modular multiplicative inverse without the extended Euclidean algorithm.
Important caveat: some composite numbers pass the Fermat test for certain bases (Carmichael numbers). Always use Miller-Rabin for reliable primality testing.