Euler's Phi via I-E

Combinatorics · Axiom Academy

LESSON Euler's Phi via Inclusion-Exclusion Deriving Euler's totient function φ(n) by counting coprime integers using the inclusion-exclusion principle We want to count integers from 1 to n that are coprime to n. Let's start with an example: n = 12 = 2² × 3. The prime factorization is crucial because a number is coprime to 12 if and only if it's not divisible by 2 or 3. 2. Applying Inclusion-Exclusion Start with all n numbers. Then subtract those divisible by each prime, add back those divisible by pairs (we subtracted them twice), subtract triplets, and so on. For n = 12 with primes p₁ = 2 and p₂ = 3: How many numbers from 1 to n are divisible by prime p? Exactly n/p numbers. For n = 12: there are 12/2 = 6 multiples of 2, and 12/3 = 4 multiples of 3, and 12/6 = 2 multiples of both. For n with prime factorization p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ, we can factor out n and express φ(n) as a product over the primes:

This is the written version of the interactive lesson above. See the full Combinatorics course.