0
$\begingroup$

I am looking for multiple proofs of that statement: here $\phi(n)$ denotes the Euler’s totient $$\sum_{d|n}{\phi(d)}=n$$

Here’s one:

By unique factorisation theorem: $n=\prod_{k=1}^{m}{p_k^{\alpha_k}}$ and $d=\prod_{k=1}^{m}{p_k^{\beta_k}}$ where $0\leq \beta_k\leq \alpha_k$ so:

\begin{align} \sum_{d|n}{\phi(d)}&=\sum_{0\leq \beta_k\leq \alpha_k}{\phi\left(\prod_{k=1}^{m}{p_k^{\beta_k}}\right)}\\ &= \sum_{0\leq \beta_k\leq \alpha_k}{\prod_{k=1}^{m}\phi({p_k^{\beta_k})}}\\ &=\sum_{0\leq \beta_k\leq \alpha_k}{\prod_{k=1}^{m}{(p_k^{\beta_k}-p_k^{\beta_k-1}})}\\ &=\prod_{k=1}^{m}{\sum_{0\leq \beta_k\leq \alpha_k}{(p_k^{\beta_k}-p_k^{\beta_k-1}}})\\ &= \prod_{k=1}^{m}{p_k^{\alpha_k}}\\ &=n. \end{align}

2 Answers 2

2

Other proof: let $G$ be a cyclic group of order $n$; then it has exactly $\phi(d)$ elements of order $d$ for each $d$ that divides $n$, and by Lagrange theorem, the order of each element has to divide the order of the group: but the group has $n$ elements. So you got exactly that $\sum_{d|n} \phi(d)=n$.

0

Observe that $φ$ is a multiplicative function, therefore its dirichlet convolution is multiplicative too. Since $N(n)=n$ is also a multiplicative function, it suffices to show that $N$ and $(φ*1)$ agree on all prime powers.

Now check that $\sum_{d|p^r} φ(p^r)=φ(1)+φ(p)+...+φ(p^r)=(p-1)+p(p-1)+p^2(p-1)+...+p^{r-1}(p-1)=(p-1)(1+p+p^2+...+p^{r-1})=(p-1)\frac{p^r-1}{p-1}=p^r$