1
φ(m) counts the units
The integers in 1, …, m coprime to m. They are exactly the invertible elements of ℤ_m, by “Bézout's Identity and Modular Inverses”.
Lesson · Number Theory and Cryptography · Congruences
Fermat's Little Theorem and Euler's Theorem
a^{φ(m)} ≡ 1 (mod m) when gcd(a,m) = 1, with Fermat's a^{p−1} ≡ 1 the prime case. It collapses enormous exponents and it is the theorem that makes RSA decryption work.
Fermat: a^{p−1} ≡ 1 (mod p) p prime, p ∤ a
Euler: a^{φ(m)} ≡ 1 (mod m) gcd(a, m) = 1
φ(p) = p − 1, φ(pq) = (p−1)(q−1) for distinct primes
so a^k ≡ a^{k mod φ(m)} (mod m)
The exponent rule
Core ideas
What this lesson establishes
One theorem, two names, and the single most useful computational fact in the course.
2
Exponents reduce modulo φ(m)
Not modulo m. 7^100 mod 10 becomes 7^{100 mod 4} = 7^0 = 1, because φ(10) = 4.
3
Coprimality is required
2^{φ(4)} = 2² = 4 ≡ 0 (mod 4), not 1. The theorem says nothing about bases sharing a factor with the modulus.
The material
Fermat and Euler
The totient, both theorems, the proof, and the consequences.
Definition · Euler's totient
φ(m) is the number of integers in {1, …, m} coprime to m. φ(1) = 1.
Theorem · Computing φ
φ(p) = p − 1 for prime p; φ(p^k) = p^k − p^{k−1}; and φ is multiplicative on coprime arguments, so φ(mn) = φ(m)φ(n) when gcd(m,n) = 1. In general φ(n) = n Π_{p | n} (1 − 1/p).
The multiplicativity is the Chinese remainder theorem in disguise: ℤ_{mn} ≅ ℤ_m × ℤ_n for coprime moduli, and an element is invertible in the product exactly when both components are. The product formula is inclusion and exclusion over the prime divisors, from “The Inclusion-Exclusion Principle” in Combinatorics and Counting.
φ(7) = 6 prime
φ(9) = 9 − 3 = 6 = 3² − 3
φ(12) = 12(1−½)(1−⅓) = 4 {1, 5, 7, 11}
φ(35) = φ(5)φ(7) = 4 · 6 = 24
φ(3120) = φ(2⁴·3·5·13) = 8 · 2 · 4 · 12 = 768
Theorem · Euler's theorem
If gcd(a, m) = 1 then a^{φ(m)} ≡ 1 (mod m).
Let u₁, …, u_φ be the units modulo m — the residues coprime to m. Multiplying each by a gives au₁, …, au_φ, which are again units (a product of units is a unit) and are distinct, since a is invertible and cancellation holds for units.
So {au₁, …, au_φ} is the same set as {u₁, …, u_φ} modulo m, and their products agree: a^φ · (u₁⋯u_φ) ≡ u₁⋯u_φ (mod m).
The product of the units is itself a unit, so it may be cancelled, leaving a^{φ(m)} ≡ 1.
□
Theorem · Fermat's little theorem
If p is prime and p ∤ a then a^{p−1} ≡ 1 (mod p). Equivalently, a^p ≡ a (mod p) for every a.
This is Euler with m = p, since φ(p) = p − 1. The second form holds even when p | a, because both sides are then 0.
Reducing exponents
Theorem · The exponent rule
If gcd(a,m) = 1 then a^k ≡ a^{k mod φ(m)} (mod m).
Example · A large exponent
7^{1000} mod 13. φ(13) = 12 and 1000 = 83·12 + 4, so 7^{1000} ≡ 7⁴ (mod 13). And 7² = 49 ≡ 10, 7⁴ ≡ 100 ≡ 9. The answer is 9, from two multiplications.
Combined with “Modular Exponentiation”'s fast exponentiation this makes essentially any modular power computable: reduce the exponent by φ(m) first, then square and multiply.
Primality testing
Fermat's theorem gives a test: if a^{n−1} ≢ 1 (mod n) for some a coprime to n, then n is definitely composite. The converse fails — Carmichael numbers such as 561 pass for every coprime base while being composite — which is why the Miller–Rabin refinement is used in practice.
This is what makes RSA key generation possible: random 1024-bit numbers are tested until one passes, and about one in 700 does. Nothing factorises anything.
Interactive
Number theory workbench
Algorithms with their traces
Method
Using the theorems
Check coprimality, compute φ, reduce the exponent.
1
Check gcd(a, m) = 1
Without it neither theorem applies. The powers of a non-coprime base never return to 1.
2
Compute φ(m)
From the factorisation of m, using multiplicativity and φ(p^k) = p^k − p^{k−1}.
3
Reduce the exponent modulo φ(m)
a^k ≡ a^{k mod φ(m)}. This is the step that turns an impossible computation into a small one.
4
Compute the small power
By square and multiply if it is still large. Usually it is trivial.
Fermat and Euler
Score 0 / 0Choose the answer you can justify.
3^{1234567} mod 100
An exponent with seven digits, reduced to one.
gcd(3, 100) = 1 ✓ theorem applies
φ(100) = φ(2²)·φ(5²) = (4−2)·(25−5) = 2 · 20 = 40
1234567 mod 40 = 7 (1234567 = 30864·40 + 7)
So 3^{1234567} ≡ 3⁷ (mod 100)
3⁷ = 2187 ≡ 87 (mod 100)
The last two digits of 3^{1234567} are 87.
That number has over half a million digits.
Two facts made this possible: Euler reduced the exponent from 1 234 567 to 7, and modular reduction kept every intermediate below 10 000. Either alone would have been insufficient.
Common mistakes
1
Reducing the exponent modulo mIt reduces modulo φ(m). 2^{10} mod 7: reducing the exponent modulo 7 gives 2³ = 8 ≡ 1; reducing modulo φ(7) = 6 gives 2⁴ = 16 ≡ 2, and 1024 = 146·7 + 2 confirms the second. The two rules sometimes agree by accident, which is what makes the wrong one survive.
2
Applying the theorem to a non-coprime base2^{φ(4)} = 4 ≡ 0 (mod 4). Coprimality is a hypothesis, not a formality.
3
Assuming passing Fermat's test proves primalityCarmichael numbers pass for every coprime base. The test proves compositeness when it fails and proves nothing when it passes.
Check your understanding
✓
Finish when you reduce the exponent before anything else.
Compute 2^{1000000} mod 77. φ(77) = 60, so the exponent becomes 1000000 mod 60 = 40, and 2^40 mod 77 is a short square-and-multiply.
Note: Euler's theorem is exactly what makes RSA work: choosing d with ed ≡ 1 (mod φ(n)) means m^{ed} = m^{1 + kφ(n)} ≡ m for m coprime to n. “RSA Encryption” puts it to use.