Prove that $\sum_{d|n}\phi(d)=n$ where $\phi$ is the Euler's phi function, $n,c\in\mathbb{N}$ Here is a very elementary number theory proof using strong induction. Please mark/grade.

Prove that $$\sum_{d|n}\phi(d)=n$$where $\phi$ is the Euler's phi function, $n,d\in\mathbb{N}$

First, when n=1,$$\sum_{d|1}\phi(d)=\phi(1)=1$$
Second, assume $$\sum_{d|k}\phi(d)=k\;\forall k\lt n,\;k\in\mathbb{N}$$
and let $n=p^kq, \;p\nmid q, p$ is prime,
Then $$\sum_{d|n}\phi(d)$$
$$=\sum_{0\le j\le k,\;e|q}\phi(p^je)$$
$$=\sum_{0\le j\le k,\;e|q}\phi(p^j)\phi(e)$$
$$=\sum_{0\le j\le k}\phi(p^j)\sum_{e|q}\phi(e)$$
$$=(\phi(1)+\sum_{1\le j\le k}(p^j-p^{j-1}))q$$
$$=(1+p^k-1)q$$
$$=p^kq$$
$$=n$$
By strong induction, $$\sum_{d|n}\phi(d)=n\;\forall n\in\mathbb{N}$$
Is my proof ok? Also, is there some more elegant proof? Thank you.
 A: In the cyclic group $\mathbb Z_n$there are $\varphi(d)$ elements of order $d$ if $d|n$. Since by lagrange every element has an order that divides $n$ we conclude the number of elements in $\mathbb Z_n$ is $\sum\limits_{d|n}\varphi(d)$.
A: Your proof is correct, but can be put more succinctly by proving the more general theorem that if $f(n)$ is multiplicative[*], then:
$$g(n)=\sum_{d\mid n} f(d)$$ is also multiplicative.
So, since $\phi(n)$ is multiplicative, you only need to check that for $n=p^k$ a prime power that:
$$p^k=\sum_{d\mid p^k} \phi(d)$$
Which you've done.
[*] Multiplicative means that if $m,n$ relatively prime, then $f(mn)=f(m)f(n)$.
A: Ok, I have a more elementary proof for this 
so, lets say $$g(n) = \sum_{d|n} \phi(d)$$ where $n=p_1^{a_1} * p_2^{a_2} ..... * p_k^{a_k}$
(I'm not going to prove g(n) is multiplicative, but it is)
so $g(n) = g(p_1^{a_1}) * ..... * g(p_k^{a_k})$.
now, each term in this pi summation of the form $$g(p_k^{a_k}) = \sum_{d|(p_k^{a_k})} \phi(d) = \phi(1) + \phi(p_k)+....+ \phi(p_k^{a_k})$$ as these are the divisors of $p_k^{a^k}$.
Now, because of the nature of the totient function, $\phi(p^j) = p^j-p^{j-1}$ (this has a relatively simple proof - of $p^j$ possible factors, there are  $p^{j-1}$ multiples of p which are less than $p^j$.  So there are $p^j-p^{j-1}$ relatively prime numbers less than $p^j$)
Anyway, if we use this to simply the summation of $\phi(d)$,we get $1+(p_k-1)+(p_k^2-p_k)+....+(p_k^{a_k}-p_k^{a_k-1}) = p_k^{a_k}$
Thus: $$g(n) = \prod_{k=1}^n  g(p_k^{a_k}) = \prod_{k=1}^n  p_k^{a_k} = n$$
A: Here is the cutest proof I know of this fact. Consider the $n$ fractions $$\frac{1}{n},\frac{2}{n} \ldots \frac{n}{n}$$
There are $\varphi(n)$ fractions which do not reduce at all. In fact, for every $d|n$, there are $\phi(d)$ fractions which reduce by exactly $n/d$. How many fractions do you have?
