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} \]