Computing Euler's Phi

Number Theory · Axiom Academy

EXAMPLE Computing Euler's Phi Function Step-by-step examples of calculating φ(n) for different types of integers Excellent work! You've mastered computing Euler's phi function. Here's what we learned: Prime factorization is key: Always start by expressing n as a product of prime powers: n = p₁^a₁ · p₂^a₂ · ... · pₖ^aₖ Euler's product formula: Use φ(n) = n · (1 - 1/p₁) · (1 - 1/p₂) · ... · (1 - 1/pₖ) where p₁, p₂, ..., pₖ are the distinct prime divisors of n Special cases to remember: For a prime p: φ(p) = p - 1 For a prime power p^k: φ(p^k) = p^k - p^(k-1) = p^(k-1)(p - 1) Multiplicative property: If gcd(m,n) = 1, then φ(mn) = φ(m)·φ(n) Systematic approach: Work step-by-step through factorization, formula application, and simplification to avoid errors Practice computing φ(n) for different values to build fluency with this fundamental number-theoretic function!

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