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

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

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?

Here is a proof using induction on $n$. The case $n=1$ is clear as $\phi(1)=1$.

Let $n>1$ and assume the result for positive integers less than $n$. Choose a prime divisor $p$ of $n$ and write $n=mp^k$ for $m$ and $p$ coprime. The divisors of $n$ are precisely the $dp^i$ for $d|m$ and $0\leq i\leq k$, so we obtain

\begin{align*} \sum_{d|n}\phi(d)&=\sum_{i=0}^{k}\sum_{d|m}\phi(dp^i)=\sum_{i=0}^{k}\phi(p^i)\sum_{d|m}\phi(d)=m\sum_{i=0}^{k}\phi(p^i)\\ &=m\left(1+\sum_{i=1}^{k}(p^i-p^{i-1})\right)=mp^k=n. \end{align*}