Properties of Euler's Phi

Number Theory · Axiom Academy

LESSON Properties of Euler's Phi Function Discover the multiplicative property, product formula, and divisor sum identity 1. The Multiplicative Property One of the most important properties of φ is that it is multiplicative : when m and n are coprime (meaning gcd(m,n) = 1), we have: This means that to compute φ(mn) for coprime m and n, we can simply multiply φ(m) and φ(n). For example, since gcd(3,5) = 1, we have φ(15) = φ(3·5) = φ(3)·φ(5) = 2·4 = 8. Using the multiplicative property, we can derive an explicit formula for φ(n). If n has the prime factorization n = p₁^a₁ · p₂^a₂ · ... · pₖ^aₖ, then: For example, φ(60) = φ(2²·3·5) = 60·(1 - 1/2)·(1 - 1/3)·(1 - 1/5) = 60·(1/2)·(2/3)·(4/5) = 16. A beautiful identity involving φ states that if we sum φ(d) over all positive divisors d of n, we get n itself: For instance, the divisors of 12 are 1, 2, 3, 4, 6, 12 , and we can verify: φ(1) + φ(2) + φ(3) + φ(4) + φ(6) + φ(12) = 1 + 1 + 2 + 2 + 2 + 4 = 12. This identity has a beautiful interpretation: every integer from 1 to n belongs to exactly one "equivalence class" determined by gcd(k,n). The φ(d) values count how many integers in each class have gcd equal to n/d.

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