eulers-totient.md

--- title: Euler's totient lead: Phi of n counts how many of the numbers 1 to n share nothing with n; it sinks for numbers with many small factors and hits its ceiling at every prime. prerequisites: greatest-common-divisor ---

Write out the numbers from 1 to n and keep only the ones coprime to n, the ones whose greatest common divisor with n is 1. The count of survivors is Euler's totient, written phi(n).

Try n = 12. Strike the even numbers and the multiples of 3, and 1, 5, 7 and 11 are left. So phi(12) = 4. Try n = 10 and 1, 3, 7 and 9 survive, so phi(10) = 4 as well.

The value at 1 is 1, since the only number in the list is 1 itself and 1 shares nothing with anything. It is a convention that pays for itself everywhere else.

A prime is the easy case. If p is prime, nothing below it shares a factor with it, so every one of 1 to p - 1 survives and phi(p) = p - 1. That is the ceiling: no n above 1 can do better, because n itself always fails the test.

A prime power is nearly as easy. To count what survives 9, strike only the multiples of 3, which are 3, 6 and 9, leaving 6. In general phi(p^k) = p^k - p^(k-1), one in every p struck out and the rest kept. So phi(8) = 8 - 4 = 4 and phi(27) = 27 - 9 = 18.

Two coprime numbers multiply cleanly. If a and b share nothing then phi(a b) = phi(a) phi(b). Check it on 12, which is 4 times 3: phi(4) = 2 and phi(3) = 2, and 2 times 2 is 4, which is what the strike-out above gave. Check it on 15, which is 3 times 5: phi(3) = 2 and phi(5) = 4, and 2 times 4 is 8.

The coprime condition is not decoration. 8 is 4 times 2, but phi(4) phi(2) = 2 times 1 = 2 while phi(8) = 4. The rule fails because 4 and 2 overlap, and the prime power rule is what you use instead.

Those two rules together compute anything. Split n into prime powers, take the totient of each, multiply. For 60, which is 4 times 3 times 5, that is 2 times 2 times 4, so phi(60) = 16. The same sum written as one formula is n multiplied by (1 - 1/p) for each distinct prime p dividing n.

The figure draws phi(n) as a bar for every n from 1 to 60, with a hairline running along the ceiling n - 1. The yellow bars are the ones that touch the hairline. They touch it exactly at the primes, since phi(n) = n - 1 says every smaller number is coprime to n, which says n has no factor to share.

The blue bars fall away from the line in a pattern you can read. The deepest dips are the numbers made of many small primes: 30 and 60 each keep only a little over a quarter of their range, because they lose half to 2, then a third of what is left to 3, then a fifth of that to 5. Numbers that are a prime times a prime sit close under the line, and the whole picture fans out into bands rather than scattering.

In the tree

The totient is the counter behind the Farey sequence: the fractions a new denominator n adds are exactly the a/n in lowest terms, so the row grows by phi(n) and the prime rows grow the most. The Farey stack note turns that into a reading of primality off the stack, and pi out of the stack counts the coprime points of the whole grid as a running sum of totients before inverting the density into pi.