How do I prove this theorem I found on the Wikipedia article about 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…
Best Answer
$$\sum_{\substack{1\leq k\leq n\\(k,n)=1}} (n-k) = \sum_{\substack{1\leq k\leq n\\(k,n)=1}} k$$
Thus:
$$\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.$