# $n\phi(n)$ with $\phi$ the totient function

How do I prove this theoreme I found on the Wikipedia article of Euler's totient function:

$$\frac{1}{2}n\phi(n)=\sum_{\begin{matrix}1\leq k \leq n \\ \gcd(k,n)=1\end{matrix}} k$$

I am aware, that $$\phi(n)=\sum_{\begin{matrix}1\leq k \leq n \\ \gcd(k,n)=1\end{matrix}} 1$$

but I am not sure what to do from here...

• You will need theorems of Dirichlet convolution. – orion May 12 '14 at 12:28
• @orion No, you won't. – Thomas Andrews May 12 '14 at 12:29
• Oh. I foolishly took a blind and longer road. – orion May 12 '14 at 12:32
• Note, it is only true if $n>1.$ – Thomas Andrews May 1 '18 at 14:53

$$\sum_{\substack{1\leq k\leq n\\(k,n)=1}} (n-k) = \sum_{\substack{1\leq k\leq n\\(k,n)=1}} k$$
\begin{align}n\phi(n) &= n \sum_{\substack{1\leq k\leq n\\(k,n)=1}} 1\\ &= \sum_{\substack{1\leq k\leq n\\(k,n)=1}} n \\&= \sum_{\substack{1\leq k\leq n\\(k,n)=1}}(n-k) + \sum_{\substack{1\leq k\leq n\\(k,n)=1}} k \\&= 2\sum_{\substack{1\leq k\leq n\\(k,n)=1}} k\end{align}
Note, the first equality is only true for $n>1$, since when $n=1$ you have that $(1,1)=1$ so the left side is $1-1$ and the right side is $1.$