Past exam of the options I course of the University of Oxford / 2012 / C (Number Theory)

For a positive integer $n$, Euler's totient function counts the integers in a complete residue system that are coprime to $n$:For $n>1$ this is equally the count with $0<k<n$. The convention gives $\phi (1)=1$.

Let $R_n=\{k\in \mathbb{Z}:0<k<n,\gcd (k,n)=1\}$. The map $k\mapsto n-k$ sends $R_n$ to itself becauseApplying it twice returns $k$, so it is a bijection. Reindexing the finite sum by this bijection givesThere is no need to assume that every residue belongs to a pair of distinct elements; the reindexing also handles the fixed point when $n=2$.

Write $S={\sum }_{k\in R_n}k$. Adding the two equal sums from part (b), and using $|R_n|=\phi (n)$, givesThereforeEquivalently, the average of the positive reduced residues is $n/2$, a consequence of their symmetry under reflection about that midpoint.

The positive integers below $30$ coprime to $30$ areThere are eight, so $\phi (30)=8$. Their sum can be grouped into four pairs summing to $30$:This agrees with the formula.