Sum of reduced residues
= Sum of reduced residues
{title2=$\sum_{1\leq j<n,\ (j,n)=1}j=n\varphi(n)/2\quad(n>1)$}
The map $j\mapsto n-j$ is a <bijection> of the <integers> between one and $n-1$ that are <coprime> to $n$. If their sum is $S$, this <bijection> gives $S=n\varphi(n)-S$, so $S=n\varphi(n)/2$. This works even at $n=2$, where the single residue is fixed. The same identity follows from the <weighted inclusion-exclusion principle> by excluding multiples of the <prime factors> of $n$.