Prueba de que $\displaystyle\sum_{d|n}\phi (d)=n:$
Lema: $\phi(a)\phi(b)=\phi(ab)$ si $(a,b)=1$ .
Prueba (editada): $\phi(n)$ es el número de generadores de $C_n$ . En particular, el número de generadores de $C_{ab}$ es $\phi(ab)$ . Tenga en cuenta que si $(a,b)=1$ puis $C_{ab}\cong C_a\times C_b$ .
Para cualquier generador $\alpha,\beta$ de $C_a,C_b$ respectivamente, $(\alpha,\beta)$ genera $C_{ab}$ , ya que: $$\text{ord}(\alpha,\beta)=\text{lcm}(\text{ord} \,\alpha,\text{ord}\,\beta)=\text{lcm}(a,b)=ab$$ El número de pares de generadores $(\alpha,\beta)$ es $\phi(a)\phi(b)$ lo que demuestra la afirmación.
Nota (en respuesta al comentario de DonAntonio): Toma de WLOG $x$ donde $\langle x\rangle$ es un subgrupo propio de $C_a\;($ así que $\text{ord}\,x<a)$ y $y\in C_b$ . Por Lagrange $\text{ord}\,x|a,\text{ord}\,y|b\Rightarrow (\text{ord}\,x,\text{ord}\,y)=1$ Así que..:
$$\text{ord}(x,y)=\text{ord}\,x\cdot\text{ord}\, y<a\,\text{ord}\, y\leq ab$$
Por lo tanto, $(x,y)$ no puede generar $C_{ab}$ .
Propuesta: $\sum_{d|n}\phi (d)=n$
Prueba: Por inducción. $n=1:\;\sum_{d|1}\phi (d)=\phi(1)=1$ . Supongamos que $\sum_{d|k}\phi (d)=k$ se mantiene para $n< k$ . Si $k=p^n,\;p$ primo, entonces: $$\begin{aligned}\sum_{d|k}\phi(d)&=\sum_{j=0}^n \phi(p^j)=1+\sum_{j=1}^n (p^j-p^{j-1})=p^n\end{aligned}$$ y hemos terminado. De lo contrario, escriba $k=p^mq$ para algún primo $p$ , donde $m$ es la mayor potencia de $p$ dividiendo $k$ y $q>1$ . Entonces $q<k$ y por nuestro lema: $$k=p^m q=\left(\sum_{d|p^m}\phi(d)\right)\left(\sum_{d|q}\phi(d)\right)=\sum_{j=0}^m\phi(p^j)\sum_{d|q} \phi(d)=\sum_{j=0}^m\sum_{d|q}\phi(p^j d)$$ Dado que cada divisor de $k$ se puede escribir $p^jd$ para algunos $d|q$ y $0\leq j\leq m$ esta suma es sobre todos los divisores de $k$ (de hecho, ninguno se cuenta más de una vez). Por lo tanto, $\sum_{d|k}\phi(d)=k$ y hemos terminado.
Sé que hay otras pruebas de esto, y que la mayoría son más sencillas, pero esto es lo que me resultó más natural cuando me planteé el problema como ejercicio. ¿Puedo comprobar que funciona y que el argumento es suficientemente claro? ¿Hay alguna mejora que pueda hacer?
Editar: Ahora me doy cuenta de que es un poco impar utilizar un argumento de teoría de grupos para el lema pero no para la proposición $-$ esto se debe a que mi intento inicial de demostrar el lema (puramente teórico de los números) era defectuoso: después de que esto fuera señalado por benh, la prueba actual es la que se me ocurrió. Dejaré la segunda parte como estaba.
