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

Proof of Fermat's Little Theorem

Prove Fermat's Little Theorem using the observation that {a, 2a, 3a, ..., (p-1)a} is a permutation of {1, 2, ..., p-1} mod p.

Proof of Fermat's Little Theorem

You'll learn a beautiful proof showing why a^(p-1) ≡ 1 (mod p) for any prime p and integer a not divisible by p.

The Core Idea

Fermat's Little Theorem states that if p is prime and a is not divisible by p, then a^(p-1) ≡ 1 (mod p). The proof hinges on a clever observation: when you multiply the numbers {1, 2, 3, ..., p-1} by a, you simply rearrange them modulo p—you get the same set, just scrambled.

The Proof

Consider the set of non-zero residues: {1, 2, 3, ..., p-1}.

Now multiply each element by a: {a, 2a, 3a, ..., (p-1)a}.

Claim: These are just a permutation of {1, 2, ..., p-1} modulo p.

Why?

  • None equals 0 (mod p), since a isn't divisible by p and neither are 1 through p-1
  • No two are equal: if ia ≡ ja (mod p) with i ≠ j, we could cancel a (using modular inverses), getting i ≡ j (mod p)—impossible for distinct values in our range

Since both sets contain the same p-1 elements modulo p, their products must be equal:

a · 2a · 3a · ... · (p-1)a ≡ 1 · 2 · 3 · ... · (p-1) (mod p)

Simplify the left side:

a^(p-1) · (1 · 2 · 3 · ... · (p-1)) ≡ (1 · 2 · 3 · ... · (p-1)) (mod p)

Since (p-1)! is not divisible by p, we can divide both sides by it:

a^(p-1) ≡ 1 (mod p)

Key Takeaway: Fermat's Little Theorem follows from the fact that multiplying {1, 2, ..., p-1} by any a coprime to p merely permutes the set modulo p, allowing us to compare products and cancel to reveal a^(p-1) ≡ 1 (mod p).