# How to prove $n*\varphi(n)/2$ sum?

how do I prove The second formula from Euler's totient function ?

$$\sum_{\substack{1\le k\le n\\(k,n)=1}} k=\frac 12 n \varphi(n)$$ for $n>1$.

-

We know that there are exactly $\phi(m)$ integers less than $m$ and relatively prime to $m$. Also if $a<m$ and $(m,a)=1$ then clearly $m-a<m$ and $(m,m-a)=1.$ Thus there are exactly $\phi(m)$ integers $a_{1},a_{2},...,m-a_{2},m-a_{1}$ less than $m$ and relatively prime to $m$. Let $$S=a_{1}+a_{2}+...+(m-a_{3})+(m-a_{2})+(m-a_{1})$$ Now writing the above term in reverse order, we get, $$S=(m-a_{1})+(m-a_{2})+...+a_{2}+a_{1}$$ Adding above two results, $$2S=m+m+...+m(\phi(m)\text{ terms})$$ $$\therefore S=\frac{m\phi(m)}{2}$$ It implies that the sum of $\phi(m)$ positive integers which are less than $m$ and relatively prime to $m$ is $\frac{m\phi(m)}{2}$.
If $0<k<n$ and $\gcd(k,n)=1$ then $\gcd(n-k,n)=1$ and $k+(n-k)=n$.
I fail to see how the equality follows from this. I know that $\sum_{1\leq k\leq n}k=\frac{n(n+1)}{2}$, but it seems that for this case, the $n+1$ term is replaced by $\varphi(n)$. – EsX_Raptor Apr 16 '12 at 15:21