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

Introduction to Fermat's Little Theorem

Statement and meaning of Fermat's Little Theorem: if p is prime and a is not divisible by p, then a^(p-1) ≡ 1 (mod p).

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.