Introduction to Fermat's Little Theorem
You'll learn one of number theory's most elegant and powerful results about primes and exponents.
What Fermat's Little Theorem Says
Fermat's Little Theorem is a beautiful statement about what happens when you raise numbers to powers modulo a prime. Here it is:
If p is a prime number and a is any integer not divisible by p, then:
a^(p-1) ≡ 1 (mod p)
In plain English: when you take any number a (that doesn't share a factor with prime p), raise it to the power (p-1), and divide by p, you always get remainder 1.
Understanding Through Examples
Let's use p = 7 (a prime) and a = 2:
- We compute 2^(7-1) = 2^6 = 64
- Dividing: 64 = 9 × 7 + 1
- So 2^6 ≡ 1 (mod 7) ✓
Try p = 5 and a = 3:
- We compute 3^(5-1) = 3^4 = 81
- Dividing: 81 = 16 × 5 + 1
- So 3^4 ≡ 1 (mod 5) ✓
Why It Matters
This theorem is remarkably predictable: no matter which a you pick (as long as p doesn't divide it), raising it to the (p-1) power always "resets" to 1 in modular arithmetic. Think of it like a clock with p hours—after exactly (p-1) ticks, certain patterns always return to their starting position.
This result has profound applications: it helps us compute large powers efficiently, test for primality, build cryptographic systems, and prove deeper theorems in number theory.
Key Takeaway: Fermat's Little Theorem states that for prime p and integer a not divisible by p, we always have a^(p-1) ≡ 1 (mod p)—a surprising regularity that makes primes special.