Discrete Math · Undergraduate
Fermat's Little Theorem and Euler's Theorem
Quick answer
Fermat's little theorem says that if p is prime and p does not divide a, then a^(p−1) ≡ 1 (mod p). Euler's theorem extends it to any modulus: if gcd(a, n) = 1, then a^φ(n) ≡ 1 (mod n). So to reduce a huge power, divide the exponent by p − 1 or φ(n) and keep only the remainder. 3¹⁰⁰ mod 7 becomes 3⁴ mod 7 = 4. The theorems also give inverses, a⁻¹ ≡ a^(p−2), and they are the reason RSA decryption works.
What you'll learn
- State Fermat's little theorem and Euler's theorem
- Reduce large exponents modulo p − 1 or φ(n)
- Find last digits of large powers
- Find modular inverses with a^(p−2)
Powers come back to 1
Fermat’s little theorem. If is prime and , then
Euler’s theorem. If , then , with the totient. For a prime, , so Fermat is the special case.
To reduce , write . Then .
Why the powers return to 1
List the residues coprime to . Multiplying each by gives , which are again coprime to and all different, since has an inverse mod . So the second list is the first list reordered, and their products agree: . Cancelling the product, which is coprime to , leaves . The same fact is Lagrange’s theorem for the group of units mod .
Worked examples
Common mistakes
Practice problems
-
Find .
Answer
Full solution
and .
-
Find .
Answer
Full solution
, and .
-
Find .
Answer
Full solution
, and .
-
Find .
Answer
Full solution
, and .
-
Find the last digit of .
Answer
Full solution
and , so .
-
Use to find the inverse of modulo .
Answer
Full solution
. Check: .
-
Find .
Answer
Full solution
and , so . Then and .
-
A student reasons that , since . Find .
Answer
Full solution
is not prime and . In fact , so every power of is mod .
Frequently asked questions
What does Fermat's little theorem say?
If p is prime and p does not divide a, then a^(p−1) ≡ 1 (mod p). Equivalently, aᵖ ≡ a (mod p) for every integer a.
What does Euler's theorem say?
If gcd(a, n) = 1, then a^φ(n) ≡ 1 (mod n), where φ is Euler's totient.
How do I compute 3¹⁰⁰ mod 7?
3⁶ ≡ 1 (mod 7) and 100 = 6 · 16 + 4, so 3¹⁰⁰ ≡ 3⁴ = 81 ≡ 4 (mod 7).
How do the theorems give inverses?
From a^(p−1) ≡ 1, the inverse of a mod p is a^(p−2).