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

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