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

Claim:Number of positive integers pair $(a, b) $ satisfying :
$n=a+b$ (for given $n$) 
$\gcd(a, b) =d$ and $d|n$
is $\phi(n/d) $. 
Proof: 
Let $a=xd$ and $b=yd$
We want number of solution for
$x+y=\frac{n}{d}$ such that $\gcd(x, y) =1$.
$\gcd(x,y)=\gcd(x,x+y)=\gcd(x,n/d)=1$
Solution for $x+y=n/d$,  $\gcd(x,y)=1$ is $\phi(n/d) $. 
                  ________________________
Number of positive integers pair $(a, b) $ satisfying $a+b=n$ is $n$. 
But this can counted in different way:
If $(a, b) $ is solution then $\gcd(a, b) =d$ for some divisor $d$ of $n$. 
So we can use our claim to write 
$\sum_{d|n} \phi(n/d) =\sum_{d|n}\phi(d)=$ Number of solution $=n.$
