Course contentsShow
← Mathematics
Lesson 2742 of 3,12154. Number TheoryFree lesson

Verifying Fermat's Little Theorem with Examples

Compute powers modulo primes to verify Fermat's Little Theorem holds for specific values of a and p.

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.