# Is there a direct, elementary proof of $n = \sum_{k|n} \phi(k)$?

If $k$ is a positive natural number then $\phi(k)$ denotes the number of natural numbers less than $k$ which are prime to $k$. I have seen proofs that $n = \sum_{k|n} \phi(k)$ which basically partitions $\mathbb{Z}/n\mathbb{Z}$ into subsets of elements of order $k$ (of which there are $\phi(k)$-many) as $k$ ranges over divisors of $n$.

But everything we know about $\mathbb{Z}/n\mathbb{Z}$ comes from elementary number theory (division with remainder, bezout relations, divisibility), so the above relation should be provable without invoking the structure of the group $\mathbb{Z}/n\mathbb{Z}$. Does anyone have a nice, clear, proof which avoids $\mathbb{Z}/n\mathbb{Z}$?

-
–  Martin Sleziak Mar 22 '14 at 5:34

Clearly $n$ counts the number of elements in the set $\{1,\ldots,n\}$. This suggests that to get a combinatorial proof we should count the number of elements in this set in a different way and get $\sum_{k \mid n} \varphi(k)$.

For $k \mid n$, let $S(k)$ be the set of $m \in \{1,\ldots,n\}$ such that $\gcd(m,n) = k$. Since for all $m \in \{1,\ldots,n\}$, $\gcd(m,n)$ is a divisor of $n$, we have $\sum_{k \mid n} \# S(k) = n$.

Now I claim that for all $k \mid n$, $\# S(k) = \varphi(\frac{n}{k})$. This implies the result because as $k$ runs through all positive divisors of $n$ so does $\frac{n}{k}$. Can you see how to establish this equality?

-
Yes I can see how to establish that equality. Very nice! –  JessicaB Sep 12 '12 at 14:56
@JessicaB But this is basically the same proof as the one you mentioned in your original question, just phrased slightly differently. To say that $\gcd(m,n)=k$ is the same as saying that $m$ has order $n/k$ in the group $\mathbb{Z}/n\mathbb{Z}$. –  Ted Sep 12 '12 at 16:01
@Ted I think my question was phrased sufficiently clearly to convey that I was expecting an elementary number theory re-phrasing of "the same proof." That said, I disagree with the spirit of your assertion, for the following reason: in order to "see it from the group structure of $\mathbb{Z}/n\mathbb{Z}$," one is actually required to write a lot more. Can we really say that two proofs are 'basically the same' if they use the same ingredients, but one is much longer and introduces needless language? (order, generator, etc). –  JessicaB Sep 12 '12 at 17:46

Write the fractions $1/n,2/n,3/n \dots ,n/n$ in the simplest form and you can observe that each fraction is of the form $s/t$ where $t$ divides $n$ and $(s,t)=1$. So the number of the fractions is the same as $\sum_{k|n}{\phi(k)}$ which is equal to $n$.

-
It might be worth noting that reducing to lowest common terms does not "equalize" any of the $n$ fractions (they remain unequal as before). –  hardmath Sep 12 '12 at 14:43
@hardmath: Actually, that's not even required. Anyone who feels like $\frac24\ne\frac12$ still keeps $n$ objects with all divisors $d$ occuring as denominator etc. –  Hagen von Eitzen Sep 12 '12 at 14:52
This is perhaps my favorite proof of this result. I believe I first encountered it in Hardy and Wright's book on number theory, but I could be wrong. –  Chris Leary Sep 12 '12 at 15:07
@ChrisLeary, it's my favorite proof too. And you're right, it's in Hardy and Wright, §16.2, at least in my 5th ed. –  lhf Sep 13 '12 at 0:09

Consider all proper fractions of the form $a/n$. There are $n$ of those. When you consider their reduced forms you get fractions of the form $b/d$ with $d|n$ and $(b,d)=1$. There are $\phi(d)$ of those. The result follows.

-