Skip to content
Tutorials Center
My learning

Topics

Lesson 15 of 37 · Congruences

Fermat's Little Theorem and Euler's Theorem

Prove Fermat's little theorem and Euler's generalization a^phi(n) = 1 (mod n), use them to reduce huge exponents and find inverses, and meet pseudoprimes.

Take a prime p and any integer a that p does not divide. Raise a to the power p − 1 and divide by p: the remainder is always 1. For p = 7 and a = 3: 3⁶ = 729 = 104 · 7 + 1. This is Fermat's little theorem, announced by Pierre de Fermat in 1640. Euler generalized it to composite moduli, and the result drives modular exponentiation tricks, primality testing and RSA.

This lesson proves both theorems with one idea (multiplication permutes residues), then uses them to shrink enormous exponents.

Fermat's little theorem

Theorem. If p is prime and p ∤ a, then a^(p−1) ≡ 1 (mod p). Equivalently, for every integer a, aᵖ ≡ a (mod p).

Proof. Take the reduced residues 1, 2, ..., p − 1. Multiply each by a: a, 2a, ..., (p − 1)a. These are nonzero modulo p and pairwise distinct (if ia ≡ ja then i ≡ j by cancellation, since p ∤ a). So they are the numbers 1, ..., p − 1 in some order. Multiply them all:

a^(p−1) · (p − 1)! ≡ (p − 1)! (mod p).

(p − 1)! is a product of numbers smaller than p, so p does not divide it, and we may cancel to get a^(p−1) ≡ 1. ∎

Python Fermat in action

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Euler's theorem

Theorem. If gcd(a, n) = 1 then a^φ(n) ≡ 1 (mod n).

Proof. Same idea. Let r₁, ..., r_φ be a reduced residue system mod n. Since gcd(a, n) = 1, the products ar₁, ..., ar_φ are another reduced residue system, so their product equals the original product modulo n. Hence a^φ · (r₁···r_φ) ≡ r₁···r_φ, and the product r₁···r_φ is coprime to n, so it can be cancelled. ∎

For a prime n = p it reduces to Fermat because φ(p) = p − 1.

Python Check Euler's theorem

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Reducing exponents

If a^k ≡ 1 then a^(k·q + r) ≡ a^r. So exponents of a unit can be reduced modulo φ(n):

a^e ≡ a^(e mod φ(n)) (mod n) when gcd(a, n) = 1.

To find 7^222 mod 10: φ(10) = 4, 222 = 4·55 + 2, so 7²²² ≡ 7² = 49 ≡ 9. The last digit is 9.

For the tower 2^(3^100) mod 7: φ(7) = 6, so reduce the exponent 3¹⁰⁰ modulo 6. Since 3² = 9 ≡ 3 (mod 6), every power 3^k with k ≥ 1 is ≡ 3 (mod 6). So the answer is 2³ = 8 ≡ 1 (mod 7).

Python Shrinking exponents

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The reduction needs gcd(a, n) = 1. For example 2 and 12 are not coprime: 2^100 mod 12 is 4, but φ(12) = 4 would give 2^0 = 1. When the base shares a factor with the modulus, use the Chinese remainder theorem or work with the prime powers separately.

Inverses from Fermat and Euler

Multiply a^(φ−1) by a to get 1, so a^(φ(n) − 1) is the inverse of a mod n. For a prime p: a⁻¹ ≡ a^(p−2) (mod p). This is easy to program, though the extended Euclidean algorithm is faster and works when φ(n) is unknown.

Python Inverse by Fermat

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Fermat pseudoprimes: a warning

Fermat gives a primality test: if a^(n−1) mod n ≠ 1 for some a coprime to n, then n is certainly composite. But the converse fails. A composite n with a^(n−1) ≡ 1 is a Fermat pseudoprime to base a. For example 341 = 11 · 31 passes the test for base 2. Worse, Carmichael numbers such as 561 = 3 · 11 · 17 pass for every base coprime to n. Chapter 5 shows how to strengthen the test (Miller–Rabin).

Python Pseudoprimes and Carmichael numbers

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What is 3^100 mod 7?

    3^6 = 1 (mod 7), and 100 = 6*16 + 4, so 3^100 = 3^4 = 81 = 4 (mod 7).
  2. 2. For which modulus does a^phi(n) = 1 hold for every a coprime to n?

    Euler's theorem covers all moduli n >= 2.
  3. 3. Why does the proof of Fermat's little theorem multiply a by every nonzero residue?

    Multiplying by a unit permutes the nonzero residues, so both products agree.
  4. 4. 341 passes the Fermat test to base 2 yet is composite. What is it called?

    341 = 11 * 31 satisfies 2^340 = 1 (mod 341) despite being composite.

Summary

  • Fermat: for a prime p and p ∤ a, a^(p−1) ≡ 1 (mod p); equivalently aᵖ ≡ a for all a.
  • Euler: for gcd(a, n) = 1, a^φ(n) ≡ 1 (mod n); both follow because multiplying by a unit permutes the residues.
  • Exponents of a unit can be reduced modulo φ(n).
  • a^(p−2) is the inverse of a modulo a prime p.
  • Passing the Fermat test does not prove primality: pseudoprimes and Carmichael numbers exist.

Next: Modular Arithmetic in Practice