Euler's Totient Function via Inclusion-Exclusion
What you'll learn: How to compute φ(n) — the count of integers from 1 to n that are coprime to n — using the inclusion-exclusion principle and prime factorization.
The Core Idea
Euler's totient function φ(n) counts how many numbers in {1, 2, 3, ..., n} share no common factors with n (are coprime to n). Instead of checking each number individually, we can use inclusion-exclusion combined with n's prime factorization.
How It Works
Suppose n = p₁^a₁ · p₂^a₂ · ... · pₖ^aᵏ where p₁, p₂, ..., pₖ are distinct primes.
Strategy: Count numbers from 1 to n that are not divisible by any of the primes p₁, p₂, ..., pₖ.
Let Aᵢ = {numbers from 1 to n divisible by pᵢ}
We want to count numbers in none of these sets — exactly what inclusion-exclusion handles!
By inclusion-exclusion:
- Start with all n numbers
- Subtract |A₁|, |A₂|, ..., |Aᵏ| (numbers divisible by each prime)
- Add back |A₁ ∩ A₂|, |A₁ ∩ A₃|, ... (overcorrected for numbers divisible by two primes)
- Continue alternating...
Since |Aᵢ| = n/pᵢ and |Aᵢ ∩ Aⱼ| = n/(pᵢpⱼ), we get:
φ(n) = n - n/p₁ - n/p₂ - ... + n/(p₁p₂) + ...
This factors as:
φ(n) = n · (1 - 1/p₁) · (1 - 1/p₂) · ... · (1 - 1/pₖ)
Example
For n = 12 = 2² · 3, the primes are 2 and 3:
φ(12) = 12 · (1 - 1/2) · (1 - 1/3) = 12 · (1/2) · (2/3) = 4
The coprime numbers: {1, 5, 7, 11} ✓
Key Takeaway: Euler's totient function uses inclusion-exclusion to count coprime integers by excluding multiples of each prime factor — the formula depends only on n's distinct prime divisors.