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$.
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$.