# Prove: $\sum_{k<n, (k,n)=1} k= \frac{1}{2}n \varphi (n)$

Prove: $\sum_{k<n, (k,n)=1}k = \frac{1}{2}n \varphi (n)$

I have had strep throat and missed the lecture discussing properties of the Euler function. Any help in solving this is appreciated. Thank you!

#### Solutions Collecting From Web of "Prove: $\sum_{k<n, (k,n)=1} k= \frac{1}{2}n \varphi (n)$"

As $(r,n)=(n-r,n)$

If $(r,n)=1, (n-r,n)=1$

So we can find $n-r$ for each $r$ with $(r,n)=1$

If $S=\sum_{1\le r <n ,(r,n)=1 }r,$

$2S= \sum_{1\le r <n ,(r,n)=1 }{r+(n-r)}=n\phi(n)$ as there are $\phi(n)$ numbers $<n$ and co-prime to $n$

If $(k,n)=1,(n-k,k)=1$,too.And there are $1/2φ(n)$ pairs of these couples.