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

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

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

  • 0
    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)$.2012-04-16
  • 1
    It is a summation over φ(n)/2 pairs, each of which sum to n.2012-04-16
  • 0
    I see it now. That makes perfect sense. Thanks. :) And +1 to the OP for this question.2012-04-16