Lesson 7 of 8 · Number Theory
Fermat's Little Theorem & Euler's Totient
You've already been reducing exponents mod 4 to find units digits — Fermat's Little Theorem is the general version of that trick for any prime modulus, and Euler's totient function extends it to any modulus at all. Both turn intimidatingly large powers into a handful of small computations.
Mark your status for this lesson:
Learning objectives
- Apply Fermat's Little Theorem to reduce a huge exponent mod (p−1) when the modulus p is prime.
- Compute Euler's totient φ(n) using its multiplicative formula from n's prime factorization.
- Apply Euler's theorem to reduce exponents mod φ(n) for a composite modulus, when the base is coprime to it.
- Recognize when an exponent one short of the full cycle length gives a modular inverse directly.
The core idea
You already know that units digits of powers cycle with a short period. Fermat's Little Theorem explains exactly why, and generalizes it: for any prime p and any a not divisible by p, aᵖ⁻¹ ≡ 1 (mod p). This means the powers of a cycle with a period that divides p−1 — so reducing any exponent mod (p−1) gives the same result as the original, much larger exponent.
Euler's theorem extends this idea to any modulus n, not just primes — but the "p−1" gets replaced by φ(n), Euler's totient function: the count of integers from 1 to n that share no factor with n. When n is itself prime, φ(n) = n−1, and Euler's theorem reduces to Fermat's Little Theorem exactly.
Fermat's Little Theorem
If p is prime and p doesn't divide a: aᵖ⁻¹ ≡ 1 (mod p)
Reduce any exponent mod (p−1) before computing — the result is unchanged.
Euler's totient function
φ(n) = n(1−1/p₁)(1−1/p₂)⋯(1−1/pₖ)
Multiplicative across prime factors — compute the contribution from each prime power separately, then multiply.
Euler's theorem (the general-modulus version)
If gcd(a,n) = 1: a^φ(n) ≡ 1 (mod n)
Works for any modulus, not just primes — reduce the exponent mod φ(n) instead of mod (p−1).
Worked example 1 — Reducing an exponent with Fermat
Problem
Find 5⁸⁰ mod 13.
Key insight
13 is prime and doesn't divide 5, so reduce the exponent mod 12 first.
Solution
80 mod 12 = 8, so 5⁸⁰ ≡ 5⁸ (mod 13). Computing directly: 5⁸ ≡ 1 (mod 13).
Takeaway
This is exactly the same move as reducing exponents mod 4 for units digits — Fermat's Little Theorem just tells you the correct modulus to reduce by for any prime.
Worked example 2 — Computing φ(n)
Problem
Find φ(60).
Key insight
Factor 60 first, then apply the multiplicative formula.
Solution
60 = 2² × 3 × 5. φ(60) = 60 × ½ × ⅔ × ⅘ = 16.
Takeaway
Each distinct prime factor contributes one (1 − 1/p) term — the exponent on that prime in n's factorization doesn't change which factor appears, only the leading n.
Worked example 3 — Euler's theorem with a composite modulus
Problem
Find 7⁵⁰ mod 12.
Key insight
12 is not prime, but gcd(7,12) = 1, so Euler's theorem applies with φ(12) in place of p−1.
Solution
φ(12) = 4, and 50 mod 4 = 2, so 7⁵⁰ ≡ 7² = 49 ≡ 1 (mod 12).
Takeaway
Euler's theorem is the same move as Fermat's, just with φ(n) instead of p−1 — always check gcd(a,n)=1 first, since the theorem requires it.
Worked example 4 — Finding a modular inverse
Problem
Find the modular inverse of 6 mod 11 (that is, the x with 6x ≡ 1 (mod 11)).
Key insight
By Fermat's Little Theorem, a¹⁰ ≡ 1 (mod 11) for any a not divisible by 11 — so a⁹ is exactly a's inverse.
Solution
6⁻¹ ≡ 6⁹ (mod 11), and computing gives 6⁹ ≡ 2 (mod 11) — check: 6 × 2 = 12 ≡ 1 (mod 11). ✓
Takeaway
This is the same "one short of the full cycle" idea from the previous example, applied intentionally to find an inverse rather than stumbling into one.
Strategy notes
Always check the theorem's requirements before applying it
Fermat's Little Theorem needs p prime and p not dividing a. Euler's theorem needs gcd(a,n) = 1. Skipping this check is the single most common way to misapply either theorem.
An exponent one short of the cycle length is the modular inverse
Since aᵖ⁻¹ ≡ 1, it follows that a · aᵖ⁻² ≡ 1 — so aᵖ⁻² is a's inverse mod p. This is a fast way to find modular inverses without the extended Euclidean algorithm.
Common mistakes
Reducing the exponent mod p instead of mod (p−1)
The cycle length is p−1, not p. Reducing the exponent mod p instead of mod (p−1) is the single most common slip when first learning this theorem.
Applying Fermat's Little Theorem to a composite modulus
Fermat's Little Theorem requires a prime modulus. For a composite modulus, use Euler's theorem with φ(n) instead — the two are not interchangeable.
Forgetting to check gcd(a, n) = 1
Both theorems require the base to be coprime to the modulus. If p divides a (Fermat) or gcd(a,n) > 1 (Euler), the theorem simply doesn't apply — it doesn't give a wrong answer, it gives no guarantee at all.
Practice
20 questions across four difficulty tiers, each with a single numeric answer. Up to three tries per question before the solution is shown.