Verifying Fermat's Little Theorem with Examples
You'll learn how to confirm Fermat's Little Theorem by computing specific modular powers and checking that the theorem's prediction holds.
What We're Doing
Fermat's Little Theorem states that if p is prime and a is not divisible by p, then:
a^(p-1) ≡ 1 (mod p)
Instead of just accepting this abstractly, we can verify it by actually computing powers modulo primes using the techniques we've learned. This hands-on verification builds intuition and confidence in the theorem's validity.
Working Through Examples
Example 1: a = 2, p = 5
Since 5 is prime and gcd(2, 5) = 1, the theorem predicts:
- 2^(5-1) = 2^4 ≡ 1 (mod 5)
Let's compute: 2^4 = 16. Now 16 = 3 × 5 + 1, so 16 ≡ 1 (mod 5). ✓ Verified!
Example 2: a = 3, p = 7
Since 7 is prime and gcd(3, 7) = 1, we expect:
- 3^(7-1) = 3^6 ≡ 1 (mod 7)
Computing step-by-step using powers in modular arithmetic:
- 3^2 = 9 ≡ 2 (mod 7)
- 3^4 ≡ 2^2 = 4 (mod 7)
- 3^6 ≡ 4 × 2 = 8 ≡ 1 (mod 7) ✓ Verified!
Example 3: a = 4, p = 11
Prediction: 4^10 ≡ 1 (mod 11)
Using repeated squaring:
- 4^2 = 16 ≡ 5 (mod 11)
- 4^4 ≡ 5^2 = 25 ≡ 3 (mod 11)
- 4^8 ≡ 3^2 = 9 (mod 11)
- 4^10 = 4^8 × 4^2 ≡ 9 × 5 = 45 ≡ 1 (mod 11) ✓ Verified!
Why This Matters
These computations aren't just busy work—they demonstrate the theorem's reliability and train you in efficient modular exponentiation, a crucial skill for cryptography and computational number theory.
Key Takeaway: Verifying Fermat's Little Theorem with concrete examples confirms that a^(p-1) ≡ 1 (mod p) whenever p is prime and a is coprime to p, reinforcing both the theorem and your computational skills.