2
$\begingroup$

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

Euler's_totient_function

2 Answers 2

1

We know that there are exactly $\phi(m)$ integers less than $m$ and relatively prime to $m$. Also if a and $(m,a)=1$ then clearly m-a 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}$.

  • 0
    I hope my answer useful. @Rami2012-04-16
6

If 0 and $\gcd(k,n)=1$ then $\gcd(n-k,n)=1$ and $k+(n-k)=n$.

  • 0
    I see it now. That makes perfect sense. Thanks. :) And +1 to the OP for this question.2012-04-16