skip to content

Euler's totient phi(n) counts the integers up to n that are coprime to it - why can you read it off n's prime factorization?

level: middleimportance: should knowfreq 42%

answer

  1. a count of coprime residues
  2. same residues that are invertible
  3. break n into prime powers
  4. only multiples of p are removed
  5. multiplicative for coprime factors only

basics

~20 s

Euler's totient is multiplicative across coprime factors, so phi(n) is the product of phi over n's prime powers, and phi(p^k) = p^k - p^(k-1) because within a prime power only the multiples of p are excluded.

solid answer

~40 s

`phi(n)` counts the integers in `1..n` whose gcd with `n` is 1. Two facts make it computable without scanning anything. On a prime power, the only values sharing a factor are the multiples of `p`, and there are `p^(k-1)` of them, so `phi(p^k) = p^k - p^(k-1)`. And phi is **multiplicative on coprime arguments**: `phi(m*n) = phi(m)*phi(n)` whenever `gcd(m, n) = 1`. So factor `n` into prime powers, apply the first rule to each, and multiply. For `12 = 2^2 * 3` that gives `(4 - 2)*(3 - 1) = 4`, matching the coprime residues 1, 5, 7, 11. The coprimality condition is load-bearing: `phi(2)*phi(2) = 1` while `phi(4) = 2`.

go deeper

for a junior

Recall the shape: phi(n) counts how many values up to n share no factor with n, and for a prime that is every value below it. Being able to list the four survivors for 12 by hand is enough at this stage.

for a middle

Explain the two rules and why they compose: multiples of p are the only losses inside a prime power, and phi multiplies across coprime factors. Show the failing case for non-coprime factors rather than just naming the condition.

for a senior

Be able to say why the coprime condition holds - the pairing of residues modulo a product with pairs of residues - and note that the cost of phi(n) is the cost of factoring n, not of the arithmetic.

for a principal

The design point is which numbers you let the system compute phi of. Values you compose from primes you chose are cheap; values handed to you are not, and that asymmetry, not the formula, is what a scheme should be built around.

## What the function actually counts Euler's totient `phi(n)` is defined for a positive integer `n` as **the number of integers `k` in the range `1..n` with `gcd(k, n) = 1`** - the count of residues that share no prime factor with `n`. For every `n > 1` the value `n` itself is not coprime to `n`, so this is the same as counting the values strictly below `n`; the range `1..n` is used because it also fixes the degenerate case `phi(1) = 1`. Those coprime residues are exactly the residues that are invertible modulo `n`, so `phi(n)` is also the size of the set of invertible residues. That is why the function keeps surfacing wherever residues get multiplied rather than added: it is the size of the structure the multiplication happens in. ## Prime powers are the whole base case For a prime `p`, every value in `1..p-1` is coprime to it, so `phi(p) = p - 1`. For a prime power `p^k` the only values in `1..p^k` that share a factor with it are the **multiples of `p`**, because `p` is the only prime available to share. There are exactly `p^(k-1)` of them, namely `p, 2p, ..., p^(k-1) * p`. Hence: - `phi(p^k) = p^k - p^(k-1)`, equivalently `p^k * (1 - 1/p)`; - `phi(8) = 8 - 4 = 4`, the residues 1, 3, 5, 7; - `phi(9) = 9 - 3 = 6`, the residues 1, 2, 4, 5, 7, 8. The common slip is `p^k - k`, subtracting one value per unit of exponent. Sanity-check that on `phi(9)`: the slip gives 7, and there are plainly only 6 coprime residues. ## Multiplicativity, and the condition it carries The second rule is `phi(m * n) = phi(m) * phi(n)` **when `gcd(m, n) = 1`**, and only then. The reason it holds is the Chinese remainder correspondence: for coprime `m` and `n`, sending `x` to the pair `(x mod m, x mod n)` matches the residues modulo `m*n` one-for-one with the pairs. A value is coprime to `m*n` exactly when it is coprime to `m` and to `n` separately, so the correspondence restricts to a one-for-one match between the coprime residues modulo `m*n` and the pairs of coprime residues - which is the product formula. Drop coprimality and the correspondence collapses, and so does the formula: - `phi(2 * 2) = phi(4) = 2`, but `phi(2) * phi(2) = 1 * 1 = 1` - the smallest failing case; - `phi(4 * 6) = phi(24) = 8`, but `phi(4) * phi(6) = 2 * 2 = 4`, because `gcd(4, 6) = 2`. Splitting `n` at its **prime powers** is therefore not one decomposition among many; it is the one decomposition whose parts are guaranteed pairwise coprime. ## The recipe, and worked values 1. Factor `n` into prime powers, `n = p1^a1 * p2^a2 * ...`. 2. Apply `phi(p^a) = p^a - p^(a-1)` to each factor independently. 3. Multiply the results; the factors are pairwise coprime, so multiplicativity applies. | n | factorization | phi(n) | how it comes out | |---|---|---|---| | 7 | 7 | 6 | `7 - 1` | | 8 | 2^3 | 4 | `8 - 4` | | 9 | 3^2 | 6 | `9 - 3` | | 12 | 2^2 * 3 | 4 | `(4 - 2) * (3 - 1)` | | 15 | 3 * 5 | 8 | `2 * 4` | | 100 | 2^2 * 5^2 | 40 | `(4 - 2) * (25 - 5)` | For `n = 12` the four survivors are 1, 5, 7, 11; counting them by hand and getting 4 is the check that the formula was applied correctly, and is worth doing once. ## What the formula does and does not buy you The formula turns a count over `n` values into arithmetic on a handful of primes, so `phi` of a number you **built** from known primes is immediate no matter how large it is. The catch is the input: the recipe needs the factorization, and there is no known way to read `phi(n)` off the digits of an `n` you were merely handed. So the cost of `phi(n)` is the cost of factoring `n`, not the cost of the multiplication. A few further properties fall straight out of the same two rules: - `phi(n)` is even for every `n > 2`, since some factor contributes a `p - 1` with `p` odd, or a power of two contributes an even value; - `phi(n) = n - 1` **only** when `n` is prime - it is a characterisation of primality, not a general formula; - `phi(n)` can be far below `n` for numbers built from many small primes: `phi(30) = 8` against `n = 30`. ## The errors that actually show up - Applying `n - 1` to a composite, which overcounts everything sharing a factor. - Multiplying `phi` across a factor pair that is not coprime, such as splitting 12 as `2 * 6`. - Subtracting the exponent instead of the lower power on a prime power. - Forgetting that 1 is coprime to every `n` and is always counted.

  • What is phi(1), and why does the prime-power rule not settle it?
    `phi(1) = 1`. The number 1 has an empty factorization, so there is no prime power to apply the rule to. It is fixed by the definition instead: the range `1..1` contains one value, and `gcd(1, 1) = 1`, so the count is 1. Defining phi as a count of values strictly *below* `n` would wrongly give 0 here.
  • Give the smallest pair of factors for which phi(m*n) = phi(m)*phi(n) fails.
    `m = n = 2`. Then `phi(4) = 2` - the residues 1 and 3 - while `phi(2) * phi(2) = 1 * 1 = 1`. The identity needs `gcd(m, n) = 1`, and `gcd(2, 2) = 2`. Splitting into prime powers avoids this by construction, since distinct prime powers are always coprime.
  • Which values of n satisfy phi(n) = n - 1?
    Exactly the primes. If `n` is prime, all of `1..n-1` are coprime to it. If `n` is composite it has a divisor `d` with `1 < d < n`, and that `d` is one of the excluded values on top of `n` itself, so at least two values are lost and `phi(n) <= n - 2`.

saying these in an interview costs you the question

  • Says phi(n) = n - 1 for every n, not only for primes
  • Multiplies phi across factors that share a common divisor
  • Gives phi(p^k) = p^k - k, subtracting one per unit of exponent
  • Excludes 1 from the count, undercounting every n by one
  • Claims phi(n) requires scanning all n values and testing each gcd