Show that $\sum_{m|n}\phi(m)=n$ 
Show that $$\sum_{m|n,\; m>0}\phi(m)=n$$
  where $\phi$ is Euler's totient function.

What I did:
There are $n-\phi(n)$ elements in the set $S_1=\{m:m|n,\;0<m<n\}$. This set is nonempty if $n>1$ since $1$ is in the set. Since it is a finite set of integers, there exists a maximum, call it $n_1$. Then there are $n-\phi(n)-\phi(n_1)$ elements in the set $S_2=\{m:m|n,\;0<m<n_1\}$. Since we can continue this process until we get the empty set, then we arrive to the conclusion that $n-\sum_{m|n}\phi(m)=0$.
Is this proof correct?
The book I took it from suggests using the following facts: $\phi(m)$ counts the number of generators of the cyclic group $C_m$, that every element of $C_n$ generates a subgroup of $C_n$, and that every subgroup of $C_n$ is isomorphic to $C_m$ for some $m|n$.
 A: The intended solution seems to be this: we have $n$ elements in $C_n$. Now for each element $a$ of $C_n$, consider the subgroup $\langle a\rangle$, the cyclic subgroup generated by $a$. This is isomorphic to some $C_m$ for some $m\mid n$. Now group the elements by this $m$. Note that there are $\varphi(m)$ elements that generate $C_m$. Thus, summing across the $m$ gives the right hand side. On the other hand, we started with $n$ elements so this gives the left hand side. 
This is the algebraic version of this combinatorial proof: write down the fractions $1/n, 2/n, \dots, n/n$ and simplify them. Then, $\varphi(m)$ of the fractions will have denominator $m$, but we have $n$ fractions, so we have the desired identity. 
A: $\phi(n)$ is the number of integers relatively prime to n. So $\phi(n) - n$ is the number of integers that are not relatively prime to $n$, but not necessary divisors of $n$. But in your definition of $S_1$ you are only counting divisors of $n$.
For the proof using group theory take a look at this: 
Difficulty understanding the proof that $n=\sum_{d|n} \phi(d) $
A: Following Silverman,  first let $F (n)=\sum_{d|n}\phi (d)$ and prove $F (p^n)=p^n $(use $\phi (p^n)=p^n-p^{n-1}$ to get a "telescoping" sum).  Then use the multiplicative property of $\phi $ to get (easily) that F is multiplicative.   Then write $n={p_1}^{n_1}{p_2}^{n_2}\dots {p_k}^{n_k} $ and finish the proof...
Or you could use the method of Gauss, which is probably the slickest I've seen https://en.m.wikipedia.org/wiki/Euler%27s_totient_function.  See "divisor sum"...
