Course contentsShow
← Mathematics
Lesson 2624 of 3,12152. CombinatoricsFree lesson

Euler's Totient Function via Inclusion-Exclusion

Computing φ(n) by counting integers coprime to n using prime factorization.

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.