# 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.

#### Solutions Collecting From Web of "Prove that $\sum_{d|n}\phi(d)=n$ where $\phi$ is the Euler's phi function, $n,c\in\mathbb{N}$"

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?

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

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