Problem
NT-B2-M10-P015 Sum of Coprime Integers
#15
★★★★☆ Level 4 of 5
Prove that for \(n>1\), the sum of all positive \(a\le n\) coprime to \(n\) equals \(\frac{n\varphi(n)}{2}\).
1001 Problems in Classical Number Theory (method inspiration) · Problem 531
Pair \(a\) with \(n-a\).
If \(\gcd(a,n)=1\), then \(\gcd(n-a,n)=1\). The pair \(a,n-a\) has sum \(n\). There is no self-pair: \(a=n-a\) gives \(2a=n\), and then \(a\) is not coprime to \(n\) for \(n>2\); for \(n=2\), the sum is \(1=\frac{2\cdot 1}{2}\). Thus the \(\varphi(n)\) numbers split into \(\frac{\varphi(n)}{2}\) pairs, each with sum \(n\). The total is \(\frac{n\varphi(n)}{2}\).
A very useful pairing idea.