Skip to content
Tutorials Center
My learning

Topics

Lesson 14 of 37 · Congruences

Residue Systems and Euler's Totient Function

Understand complete and reduced residue systems mod n, define Euler's totient function phi(n), derive its product formula, and compute it in Python.

When you work modulo n, every integer is represented by a remainder from a set of n possibilities. Two sets matter. The complete residue system contains one number from every class: 0, 1, ..., n − 1 is the usual choice. The reduced residue system keeps only the classes of numbers coprime to n. Those are exactly the numbers you can multiply by and divide by without losing information.

The size of the reduced system is Euler's totient function φ(n). It appears in the exponent of Euler's theorem, in the RSA algorithm, and in counting problems. This lesson defines it, proves a formula and shows how to compute it.

Complete and reduced residue systems

For n = 12, a complete residue system is {0, 1, 2, ..., 11}. Another is {12, 13, ..., 23}, or even {−5, ..., 6}: any list with one member from each class mod 12. The reduced residue system mod 12 is {1, 5, 7, 11}: the numbers in 1..12 with gcd(k, 12) = 1.

Key fact: if gcd(a, n) = 1 and r₁, ..., rₙ is a complete residue system, then a·r₁, ..., a·rₙ is also one. Multiplying by a unit shuffles the classes without collisions. This is a restatement of the cancellation law: a·r ≡ a·s implies r ≡ s. Likewise multiplying a reduced system by a unit gives a reduced system.

Python Multiplying permutes the residues

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Only a coprime to 12 (1, 5, 7, 11) reach all 12 residues; the others hit 12 / gcd(a, 12) values only.

Euler's totient function

Definition. φ(n) is the number of integers k with 1 ≤ k ≤ n and gcd(k, n) = 1.

The first values: φ(1) = 1, φ(2) = 1, φ(3) = 2, φ(4) = 2, φ(5) = 4, φ(6) = 2, φ(7) = 6, φ(8) = 4, φ(9) = 6, φ(10) = 4, φ(12) = 4.

For a prime p, every number 1, ..., p − 1 is coprime to p, so φ(p) = p − 1. For a prime power pᵃ, the only numbers not coprime to pᵃ are multiples of p; there are pᵃ⁻¹ of them. So φ(pᵃ) = pᵃ − pᵃ⁻¹ = pᵃ⁻¹(p − 1).

Python phi by brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Multiplicativity

Theorem. If gcd(m, n) = 1 then φ(mn) = φ(m)φ(n).

The chapter on the Chinese remainder theorem proves this cleanly: a number is coprime to mn exactly when it is coprime to both m and n, and CRT pairs residues mod mn with pairs of residues mod m and mod n. For now, trust the test below.

Combining multiplicativity with the prime power formula gives the product formula: if n = p₁^a₁ ··· pₖ^aₖ then

φ(n) = n · (1 − 1/p₁)(1 − 1/p₂)···(1 − 1/pₖ).

Reading the formula: of all numbers up to n, a fraction 1/p is wiped out by each prime p dividing n. For n = 36 = 2² · 3², φ = 36 · (1/2) · (2/3) = 12.

Python Product formula and a fast phi

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last two lines show that φ(24) = 8 while φ(4)·φ(6) = 4, because 4 and 6 are not coprime.

Gauss's divisor-sum identity

A beautiful identity: the sum of φ(d) over all divisors d of n equals n. For n = 12: φ(1) + φ(2) + φ(3) + φ(4) + φ(6) + φ(12) = 1 + 1 + 2 + 2 + 2 + 4 = 12. The reason: sort the fractions k/n for k = 1, ..., n by their reduced form. The fractions with denominator d (in lowest terms) number φ(d), and d ranges over the divisors of n.

Python Check the divisor-sum identity

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Where φ shows up

  • Order of the unit group: the numbers coprime to n form a group under multiplication mod n with φ(n) elements.
  • Euler's theorem: a^φ(n) ≡ 1 (mod n) for gcd(a, n) = 1, next lesson.
  • RSA: the secret exponent is computed modulo φ(pq) = (p − 1)(q − 1).
  • Counting: the number of fractions in lowest terms with denominator n is φ(n); the number of primitive n-th roots of unity is φ(n).

Computing phi(n)

Prime p phi(p) = p - 1.
Prime power phi(p^a) = p^a - p^(a-1).
Coprime parts phi(mn) = phi(m) phi(n).
Any n n times (1 - 1/p) over primes.
1 / 2

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What is phi(10)?

    The numbers 1, 3, 7, 9 are coprime to 10.
  2. 2. What is phi(81)?

    81 = 3^4, so phi = 3^3 * (3 - 1) = 54.
  3. 3. Which of these is wrong?

    Multiplicativity needs gcd(m, n) = 1. For example phi(24) = 8 but phi(4) * phi(6) = 4.
  4. 4. What is the size of a reduced residue system modulo 15?

    phi(15) = phi(3) * phi(5) = 2 * 4 = 8.

Summary

  • A complete residue system has one number from each class mod n; a reduced system keeps only the classes coprime to n.
  • Multiplying a complete or reduced system by a unit permutes it.
  • φ(n) counts the integers in 1..n coprime to n; φ(p) = p − 1 and φ(pᵃ) = pᵃ − pᵃ⁻¹.
  • φ is multiplicative on coprime arguments, giving φ(n) = n ∏ (1 − 1/p).
  • Σ over d | n of φ(d) = n.

Next: Fermat's Little Theorem and Euler's Theorem