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 φ(n)\varphi(n) is the number of integers kk with 1≤k≤n1 \le k \le n and gcd⁡(k,n)=1\gcd(k, n) = 1. For n=12n = 12, these are 1,5,7,111, 5, 7, 11, so φ(12)=4\varphi(12) = 4.

CaseFormula
prime ppφ(p)=p−1\varphi(p) = p - 1
prime powerφ(pk)=pk−pk−1\varphi(p^k) = p^k - p^{k-1}
coprime mm, nnφ(mn)=φ(m)φ(n)\varphi(mn) = \varphi(m)\varphi(n)
any nnφ(n)=n∏p∣n(1−1p)\varphi(n) = n\displaystyle\prod_{p \mid n}\left(1 - \frac{1}{p}\right)

The product runs over the distinct primes dividing nn, found from its prime factorization.

Why the product formula works

Among 1,…,n1, \ldots, n, a fraction 1p\tfrac{1}{p} of the numbers are multiples of pp, so a fraction 1−1p1 - \tfrac{1}{p} are not. For a prime power pkp^k, the only bad numbers are the pk−1p^{k-1} multiples of pp, giving pk−pk−1=pk(1−1p)p^k - p^{k-1} = p^k\left(1 - \tfrac{1}{p}\right). For coprime mm and nn, the Chinese remainder theorem matches each number mod mnmn with a pair of remainders mod mm and mod nn, and it is coprime to mnmn exactly when both remainders are coprime, so the counts multiply. Splitting nn into prime powers and multiplying gives the formula.

Worked examples

Common mistakes

Practice problems

  1. Find φ(13)\varphi(13).

    Answer

    1212

    Full solution

    1313 is prime, so φ(13)=12\varphi(13) = 12.

  2. Find φ(16)\varphi(16).

    Answer

    88

    Full solution

    16−8=816 - 8 = 8.

  3. Find φ(45)\varphi(45).

    Answer

    2424

    Full solution

    45⋅23⋅45=2445 \cdot \tfrac{2}{3} \cdot \tfrac{4}{5} = 24.

  4. Find φ(1000)\varphi(1000).

    Answer

    400400

    Full solution

    1000⋅12⋅45=4001000 \cdot \tfrac{1}{2} \cdot \tfrac{4}{5} = 400.

  5. Find φ(77)\varphi(77).

    Answer

    6060

    Full solution

    φ(7)φ(11)=6⋅10\varphi(7)\varphi(11) = 6 \cdot 10.

  6. Find φ(210)\varphi(210).

    Answer

    4848

    Full solution

    210=2⋅3⋅5⋅7210 = 2 \cdot 3 \cdot 5 \cdot 7, so φ=1⋅2⋅4⋅6\varphi = 1 \cdot 2 \cdot 4 \cdot 6.

  7. How many fractions k25\tfrac{k}{25} with 1≤k≤251 \le k \le 25 are already in lowest terms?

    Answer

    2020

    Full solution

    k25\tfrac{k}{25} is in lowest terms when gcd⁡(k,25)=1\gcd(k, 25) = 1, and φ(25)=25−5\varphi(25) = 25 - 5.

  8. A student computes φ(12)=φ(2)φ(6)=2\varphi(12) = \varphi(2)\varphi(6) = 2. Find φ(12)\varphi(12).

    Answer

    44

    Full solution

    22 and 66 are not coprime. Use φ(4)φ(3)=2⋅2\varphi(4)\varphi(3) = 2 \cdot 2.

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.

What to learn next