Indian Statistical Institute B.Math & B.Stat : Number Theory

Let $S$ be the set of all integers $k$, $1 \leq k \leq n$, such that $g.c.d(k,n)=1$. What is the arithmetic mean of the integers in $S$?. First note that $|S| = \phi(n)$. Now let $k \in S$ then there exists intergers $u,v$ such that $ku+nv=1\dots (A)$. The integer $n-k \in \{1,2,\dots,n-1\}$ because $k$ can never be equals $n$, for $g.c.d(n,n)=n$ and $k \in S$. We will now show that $g.c.d(n-k,n)=1.$ Adding $-nu$ to both sides of $(A)$ we get $-nu+ku+nv=-nu+1 \implies -u(n-k)+(v+u)n = 1 \implies g.c.d(n-k,n)=1$ So, for $k \in \{1,2,\dots,n-1\}$ if $k \in S \implies n-k \in S$ Thus $S$ can be written in the form, $S=\{k_1,k_2,k,.....,k_r,n-k_r,......,n-k_2,n-k_1\}$ where $|S| = \phi(n)$ Clearly the sum of the elements of $S$ is $(k_1+n-k_1)+(k_2+n-k_2)+\dots+(k_r+n-k_r) = \frac{n\phi(n)}{2}$ ( Pairing reduces the terms to half the original ($\phi(n)))$. arithmetic mean $$=\frac{\frac{n\phi(n)}{2}}{\phi(n)} = \frac{n}{2}$$