Easiest proof for $\sum_{d|n}\phi(d)=n$ To prove $\sum_{d|n}\phi(d)=n$. What is the easiest proof for this to tell my first year undergraduate junior. I do not want any Mobius inversion etc only elementry proof. Tthanks!

$d\mid n \land S_d=\{m:\gcd(m,n)=d\} \implies \left\lvert S_d \right\rvert=\phi\left(\dfrac{n}{d}\right)$


*

*$S_{d_i}\cap S_{d_j}=\emptyset\ \forall i\neq j$

*$\displaystyle\bigcup_{d \mid n}S_d=\{1,2,\ldots,n\}$ 
$\therefore \left\lvert\displaystyle\bigcup_{d \mid n}S_d\right\rvert=\displaystyle\sum_{d\mid n}\left\lvert S_d\right\rvert\implies n=\displaystyle\sum_{d\mid n}\phi\left(\dfrac{n}{d}\right)=\displaystyle\sum_{d\mid n}\phi\left(d\right)$
