Discrete Math · Undergraduate
Euler's Totient Function φ(n)
Quick answer
Euler's totient φ(n) counts the integers from 1 to n that are coprime to n. For a prime, φ(p) = p − 1; for a prime power, φ(pᵏ) = pᵏ − pᵏ⁻¹, since only the multiples of p share a factor with it. When m and n are coprime, φ(mn) = φ(m)φ(n). Together these give the product formula φ(n) = n(1 − 1/p₁)(1 − 1/p₂)⋯ over the distinct primes dividing n, so φ(100) = 100 · ½ · ⅘ = 40.
What you'll learn
- Compute φ(n) by listing for small n
- Find φ of a prime and of a prime power
- Use multiplicativity for coprime factors
- Apply the product formula from the prime factorization
Counting coprime numbers
Euler’s totient is the number of integers with and . For , these are , so .
| Case | Formula |
|---|---|
| prime | |
| prime power | |
| coprime , | |
| any |
The product runs over the distinct primes dividing , found from its prime factorization.
Why the product formula works
Among , a fraction of the numbers are multiples of , so a fraction are not. For a prime power , the only bad numbers are the multiples of , giving . For coprime and , the Chinese remainder theorem matches each number mod with a pair of remainders mod and mod , and it is coprime to exactly when both remainders are coprime, so the counts multiply. Splitting into prime powers and multiplying gives the formula.
Worked examples
Common mistakes
Practice problems
-
Find .
Answer
Full solution
is prime, so .
-
Find .
Answer
Full solution
.
-
Find .
Answer
Full solution
.
-
Find .
Answer
Full solution
.
-
Find .
Answer
Full solution
.
-
Find .
Answer
Full solution
, so .
-
How many fractions with are already in lowest terms?
Answer
Full solution
is in lowest terms when , and .
-
A student computes . Find .
Answer
Full solution
and are not coprime. Use .
Frequently asked questions
What does φ(n) count?
The integers k with 1 ≤ k ≤ n and gcd(k, n) = 1.
What is φ of a prime?
p − 1, since every number from 1 to p − 1 is coprime to p.
What is the formula for φ(n)?
φ(n) = n(1 − 1/p₁)(1 − 1/p₂)⋯(1 − 1/pᵣ), where p₁, …, pᵣ are the distinct primes dividing n.
Is φ multiplicative?
Yes, for coprime factors: φ(mn) = φ(m)φ(n) when gcd(m, n) = 1. It fails otherwise: φ(4) = 2, but φ(2)φ(2) = 1.