tziaxri wrote:Prove that
\[ \forall n\geq1 : \displaystyle\mathop{\sum}\limits_{d|n}\phi(d)=n \] where: \[ \phi(n) = \rvert\bigl\{k\in \mathbb{N} \rvert 1 \leq k \leq n \wedge (k,n)=1 \bigl\}\rvert \]
is the Euler phi function.
We give the classical proof which can be found in almost every number theory book. For example: Hardy and Wright, Introduction to the Theory of Numbers.
For \(n=1\) is trivial. If \(n>1\) and \(n=\mathop{\prod}\limits_{i=1}^{k}p_i^{r_i}\) is the unique-prime-factorization of \(n\), then the divisors of \(n\) are the numbers \(d=\mathop{\prod}\limits_{i=1}^{k}p_i^{s_i}\,, \; s_i\leqslant r_i\,,\) for every prime \(p_i\). The function \[F(n):=\displaystyle\mathop{\sum}\limits_{d|n}\phi(d)\,,\quad n\in {\mathbb{N}}\,,\] is multiplicative. For every \(i=1,2,\ldots, k\,,\) we have
\begin{align*}
F(p_i^{r_i})&=\displaystyle\mathop{\sum}\limits_{j=0}^{r_i}\phi(p_i^{j})\\
&=\phi(1)+\mathop{\sum}\limits_{j=1}^{r_i}\phi(p_i^{j})\\
&=1+\mathop{\sum}\limits_{j=1}^{r_i}(p_i^{j}-p_i^{j-1})\\
&=p_i^{r_i}\,.
\end{align*} And from the multiplicity of \(F\) we have \[F(n)=\displaystyle\mathop{\prod}\limits_{i=1}^{k}F(p_i^{r_i})=\mathop{\prod}\limits_{i=1}^{k}p_i^{r_i}=n\,.\]