Course contentsShow
← Mathematics
Lesson 2747 of 3,12154. Number TheoryFree lesson

Properties and Formulas for φ(n)

Calculate φ(n) for prime powers and general n using multiplicativity and the formula φ(p^k) = p^(k-1)(p-1).

Properties and Formulas for φ(n)

What you'll learn: How to efficiently calculate Euler's totient function φ(n) using its multiplicative property and a key formula for prime powers.

The Core Idea

You already know that φ(n) counts how many integers from 1 to n are relatively prime to n. But computing this by checking every number is tedious! Fortunately, φ(n) has beautiful structural properties that make computation much faster.

The Fundamental Formula for Prime Powers

When n is a prime power (n = p^k where p is prime), there's an elegant formula:

φ(p^k) = p^(k-1)(p - 1)

Why does this work? Among the numbers 1 to p^k, the only ones that aren't relatively prime to p^k are the multiples of p. There are exactly p^(k-1) such multiples (namely p, 2p, 3p, ..., p^k). So:

φ(p^k) = p^k - p^(k-1) = p^(k-1)(p - 1)

Example: φ(27) = φ(3³) = 3²(3 - 1) = 9 × 2 = 18

Multiplicativity: The Power Tool

Here's the game-changer: φ(n) is multiplicative. If gcd(m, n) = 1, then:

φ(mn) = φ(m) · φ(n)

This means you can break n into its prime factorization and compute φ for each prime power separately, then multiply the results!

Example: Find φ(72) where 72 = 2³ × 3²:

  • φ(2³) = 2²(2 - 1) = 4
  • φ(3²) = 3¹(3 - 1) = 6
  • φ(72) = 4 × 6 = 24

The General Formula

Combining these insights, for n = p₁^k₁ × p₂^k₂ × ... × pₘ^kₘ:

φ(n) = n · (1 - 1/p₁) · (1 - 1/p₂) · ... · (1 - 1/pₘ)

Key Takeaway: Use φ(p^k) = p^(k-1)(p-1) for prime powers and multiplicativity to compute φ(n) efficiently by factoring n into prime powers, calculating φ for each, and multiplying the results together.