Totient sums

I took a bit of a break to travel to Japan for a conference, but I’m back now to continue the series I started with Post Without Words #10, a follow-up post, and Post Without Words #11. Recall that we have dots on circles with spokes, like this:

Circle n has a dot on spoke k if and only if \gcd(k,n) = 1 (the spokes are numbered from zero).

In PWW #11, I showed some pictures like this:

We have here the circles with 1, 2, 3, 4, 6, and 12 spokes—one for each divisor of 12. The colors highlight the fact that if we take all these circles and superimpose them on each other, we get exactly one dot at the end of each spoke.

Does this always happen? In fact, it does. First, as I explained in a previous post, a spoke in a particular location has a dot the first time that spoke appears, but then never again. So we can never get overlapping dots. But how do we know that if we take the circles for all the divisors of some number, we end up with all possible dots? Well, given a circle with n spokes, its spokes also show up in circles corresponding to divisors of n, and in no other circles. For example, the circle with 6 spokes above includes every other spoke from the circle with 12; the circle with 4 spokes includes every third spoke, and so on. Any circle m < n where m is not a divisor of n will have completely different spokes. So among all of the n spokes, each one must have first appeared as a spoke of some divisor of n, where it would have a dot. So if we collect the circles for all divisors of n, we necessarily include one dot for each spoke.

The number of dots on circle n can be notated by the Euler totient function \varphi(n) (also known as the Euler phi function), which counts how many numbers less than n are relatively prime to n. Using this notation, we can restate the above observation as

\displaystyle \sum_{d|n} \varphi(d) = n,

that is, if we add up the number of dots on circle d for each d which is a divisor of n, we get a total of exactly n dots.

Advertisements

About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in geometry, pattern, pictures, posts without words, proof and tagged , , , , , . Bookmark the permalink.