TITLE: Prove: $\sum_{k<n, (k,n)=1} k= \frac{1}{2}n \varphi (n)$
QUESTION [4 upvotes]: 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!

REPLY [5 votes]: 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$

REPLY [1 votes]: If $(k,n)=1,(n-k,k)=1$,too.And there are $1/2φ(n)$ pairs of these couples.
{"set_name": "stack_exchange", "score": 4, "question_id": 336593}