Euler's Totient Function & Fermat's Little Theorem

Number Theory & Cryptographic Math

Chapter 8 · Euler's Totient Function & Fermat's Little Theorem

Every prior chapter built a tool: the division algorithm, modular arithmetic, the Euclidean algorithm, modular inverses, primality testing, fast exponentiation. This chapter builds the last piece of pure theorem — the actual mathematical fact that makes RSA's encryption and decryption genuinely undo each other, not just a fact stated on faith.

Euler's Totient Function: Counting Coprimes

Euler's totient function, φ(n), counts how many integers in [1, n] are coprime to n — that is, how many satisfy gcd(k, n) = 1.

Verified directly — φ(p) for a prime

For a prime p, every integer from 1 to p−1 is automatically coprime to p (a prime has no divisors besides 1 and itself), so φ(p) = p − 1. Confirmed directly: φ(5)=4, φ(7)=6, φ(11)=10, φ(13)=12 — each exactly matching p−1.

The formula RSA actually needs: φ(pq) for two distinct primes

φ is multiplicative for coprime inputs: φ(mn) = φ(m) × φ(n) whenever gcd(m, n) = 1. Since two distinct primes are always coprime to each other, this gives φ(p × q) = (p−1)(q−1) directly.

Verified directly

φ(3×5=15) = 8, and (3−1)(5−1) = 8 — match. φ(5×7=35) = 24, and (5−1)(7−1) = 24 — match. φ(11×13=143) = 120, and (11−1)(13−1) = 120 — match.

Why "coprime" is a real requirement, not fine print

φ(4)=2 and φ(6)=2, so the naive product would suggest φ(24)=4. The actual value is φ(24)=8 — the formula genuinely fails once gcd(m,n)≠1 (here gcd(4,6)=2). This is exactly why RSA's own security depends on using two distinct primes, not any two coprime-looking numbers.

Fermat's Little Theorem, Proved — Not Just Stated

The theorem

For a prime p and any integer a not divisible by p: a^(p−1) ≡ 1 (mod p).

Chapters 6 and 7 both used this without proof. Here's the actual argument, built entirely from tools this course has already established:

The proof — a permutation argument, verified directly on p=7, a=3

Since gcd(a,p)=1, multiplying every element of {1, 2, ..., p−1} by a (mod p) just rearranges the same set — it never produces a repeat or a zero. Verified: {3,6,9,12,15,18} mod 7 = {3,6,2,5,1,4} — exactly a reordering of {1,2,3,4,5,6}. Multiplying every element of both sets together must therefore give the same product mod p: a^(p−1) × (p−1)! ≡ (p−1)! (mod p) — verified directly, both sides equal 6. Since (p−1)! is coprime to p (a product of numbers all coprime to p), Chapter 5's own modular inverse can cancel it from both sides, leaving exactly a^(p−1) ≡ 1 (mod p).

This is a genuine direct proof, in the same style Discrete Mathematics Fundamentals established — no step taken on faith, and the final cancellation step is literally Chapter 5's own modular inverse doing real work.

Verified directly, exhaustively

Checked for every a from 1 to p−1, for p ∈ {5, 7, 11, 13}: a^(p−1) mod p = 1 in every single case, no exceptions found.

Euler's Theorem: The Generalization to Any Modulus

The theorem

For any n and any a with gcd(a, n) = 1: a^φ(n) ≡ 1 (mod n).

The exact same permutation argument works, replacing "all of 1 to p−1" with "everything in [1,n] coprime to n" — that set has φ(n) elements by definition, and multiplying by any coprime a still just rearranges it. Fermat's Little Theorem is the special case where n happens to be prime (since φ(p) = p−1).

Verified directly — Euler's theorem on a composite modulus, n=15

φ(15) = 8. Checking every a coprime to 15 (1, 2, 4, 7, 8, 11, 13, 14): a⁸ mod 15 = 1 in every single case.

Real Relevance: This Is RSA's Actual Correctness Argument

Chapter 9 sets n = pq, uses φ(n) = (p−1)(q−1) (this chapter's own formula), and chooses e and d so that ed ≡ 1 (mod φ(n)) — a modular inverse, Chapter 5's own tool. Euler's theorem then guarantees m^(ed) ≡ m (mod n) for any message m coprime to n — the entire reason decrypting an RSA-encrypted message recovers the original message. Nothing about that guarantee is new material — it's this chapter's own theorem, applied.

Totient & Fermat's Little Theorem in Code

import math

def totient(n):
    return sum(1 for k in range(1, n + 1) if math.gcd(k, n) == 1)

def totient_from_primes(p, q):
    return (p - 1) * (q - 1)   # requires p, q distinct primes

print(totient(15), totient_from_primes(3, 5))   # 8 8

# Fermat's Little Theorem, verified for every a in a prime's own range
p = 13
print(all(pow(a, p - 1, p) == 1 for a in range(1, p)))   # True

# Euler's theorem, verified on a composite modulus
n = 15
phi_n = totient(n)
print(all(pow(a, phi_n, n) == 1 for a in range(1, n) if math.gcd(a, n) == 1))   # True

Hands-On Exercises

Exercise 1

Compute φ(17 × 19) using this chapter's own formula, then verify it by directly counting the integers from 1 to 17×19 that are coprime to 17×19.

📄 View solution

Exercise 2

Using this chapter's own permutation argument, verify Fermat's Little Theorem for p=11, a=4: show that {4, 8, 12, ..., 40} mod 11 is a permutation of {1,...,10}, then confirm 4^10 mod 11 = 1.

📄 View solution

Exercise 3

Explain why Fermat's Little Theorem is a special case of Euler's theorem, using this chapter's own φ(p)=p−1 fact, and verify Euler's theorem directly for the composite modulus n=21 (compute φ(21) first, then check it for at least three different values of a coprime to 21).

📄 View solution

Chapter 8 Quick Reference

Euler's totient φ(n): the count of integers in [1,n] coprime to n
φ(p) = p−1 for prime p; φ(pq) = (p−1)(q−1) for distinct primes — the exact formula RSA needs
The multiplicative property genuinely requires coprimality — verified to fail otherwise (φ(24) ≠ φ(4)×φ(6))
Fermat's Little Theorem: a^(p−1) ≡ 1 (mod p) for prime p — proved directly via a permutation argument plus Chapter 5's own modular inverse
Euler's theorem: a^φ(n) ≡ 1 (mod n) for any n with gcd(a,n)=1 — Fermat's theorem is the prime special case
This is RSA's own core correctness guarantee: m^(ed) ≡ m (mod n), assembled fully in Chapter 9
Next chapter: RSA — how the math actually works