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

Question

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}$?

Answer 1

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?

Answer 2

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$.

Answer 3

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 $\gcd(b,d)=1$. There are $\phi(d)$ of those. The result follows.

Answer 4

For a prime $p$ and $k\ge1$, $$ \phi\!\left(p^k\right)=(p-1)p^{k-1}\tag1 $$ Furthermore, the result is true for powers of a prime: $$ \begin{align} \sum_{d|p^m}\phi(d) &=\phi(1)+\sum_{k=1}^m\phi\!\left(p^k\right)\tag{2a}\\ &=1+(p-1)\sum_{k=1}^mp^{k-1}\tag{2b}\\ &=1+(p-1)\frac{p^m-1}{p-1}\tag{2c}\\[9pt] &=p^m\tag{2d} \end{align} $$ Given $(m_1,m_2)=1$, for every $d$ so that $d|m_1m_2$, that there are unique $d_1$ and $d_2$ so that $d=d_1d_2$ and $d_1|m_1$ and $d_2|m_2$. Thus, $$ \sum_{d_1|m_1}\phi(d_1)\sum_{d_2|m_2}\phi(d_2)=\sum_{d|m_1m_2}\phi(d)\tag3 $$ Therefore, since $\phi$ is multiplicative, $m\mapsto\sum\limits_{d|m}\phi(d)$ is multiplicative.

$(2)$ and $(3)$ show that $$ \sum_{d|n}\phi(d)=n\tag4 $$