Sum of Integers Relatively Prime to n
If\[d | a, \; d | n\]
then \[d | (n-a), d | n\]
and vice versa, so \[gcd(a,n)=gcd(n-a, n)\]
. Hence\[\sum_{gcd(a,n)=1} a = \sum_{gcd(n-a, a,n)=1} n-a\]
(1)There are
\[\phi (n)\]
terms in each summation - those integers \[m\]
for which \[gcd(m,n)=1\]
. Hence\[\sum_{gcd(a,n)=1} a + \sum_{gcd(n-a, a,n)=1} n-a = \sum_{gcd(a,n)=1}n = n\phi (n)\]
Then (1) implies
\[2 \sum_{gcd(a,n)=1} a =n\phi (n)\]
Hence
\[\sum_{gcd(a,n)=1} a = \frac{n\phi (n)}{2}\]