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

Question

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.

Answer 1

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?

Answer 2

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)$.

Answer 3

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)$.