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*}

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.

This proof uses Möbius inversion, and is pretty quick! Recall the function $$ \mu(n) = \begin{cases} (-1)^{\nu(n)} \qquad \text{if $n$ is square free} \\ 0 \,\,\qquad\qquad\text{otherwise}, \end{cases} $$ where $\nu(n)$ is the number of distinct prime divisors of $n$. The Möbius inversion formula says that $$ f(n)=\sum_{d\mid n} g(d) $$ if and only if $$ g(n)=\sum_{d\mid n}\mu(d)f(n/d). $$ Putting $f(n)=n$ and $g(n)=\varphi(n)$, by Möbius it suffices to show $$ \varphi(n)=\sum_{d\mid n}\mu(d)\frac{n}{d}, $$ and this is true since \begin{align*} \varphi(n)&=n \prod_{p\mid n}\bigg(1-\frac{1}{p}\bigg)\\ &=n \sum_{d\mid n}\frac{\mu(d)}{d}\\ &=\sum_{d\mid n}\mu(d)\frac{n}{d}. \end{align*}

(Note that $\prod_{p\mid n}\big(1-\frac{1}{p}\big)=\sum_{d\mid n}\frac{\mu(d)}{d}$ since terms in the sum are zero except at divisors of $d$ that consist of distinct primes, and multiplying out the product on the right gives precisely this sum.)