QUESTION: Let $S$ be the set of all integers $k$, $1\leq k\leq n$, such that $\gcd(k,n)=1$. What is the arithmetic mean of the integers in $S$?
MY APPROACH: According to the question, every number in the set will be coprime with $n$.
Clearly, if $n$ is a prime number then $S$ is the set of the first $n$ natural numbers.. If $n$ is not a prime number, then the cardinality of the set is $\text{ }\phi(n)+1$, where $\text{ }\phi(n)$ denotes Euler's totient function.
In the former case, the arithmetic mean of the set is $\frac{\frac{n(n+1)}{2}}n=\frac{(n+1)}{2}$.
But I am stuck with the later case.. $\phi(n)$ just denotes the number of numbers less than $n$ and coprime to it, but we need the sum of all such numbers to be able to compute the arithmetic mean.
How do I do that?
Note: $\phi(n)$ also works for the former case.. It's just that $\text{ }\phi(n)=(n-1)\text{ }$ when $n$ is prime.. I just did not state that explicitly..
Thank You so much for your kind help in advance..
Best Answer
The cases $n=1,2$ are anomalous, and easily handled. For $n>2$ we have that $\varphi(n)=2m$ is even.
Now, $\gcd(n,k)=1\iff \gcd(n,n-k)=1$ so we can group the elements relatively prime to $n$ into $m$ pairs each of which sums to $n$. (Note, of course, that $n$ and $n-k$ are always distinct save for the case $n=2$ and $k=1$ since, generally, $n-k=k$ would imply that $2k=n$ which would contradict $\gcd(n,k)=1)$). Thus the sum of all the $2m$ numbers relatively prime to $n$ is $m\times n$. It follows that the desired average is $$\frac {m\times n}{2m}=\frac n2$$
Oddly, this formula gives the right answer for $n=2$ though the argument isn't applicable to that case. Of course, the formula fails for the case $n=1$.
Sanity check: for $n=15$ we have $\varphi(15)=8$ and the elements in $S$ are $\{1,2,4,7,8,11,13,14\}$. It is easy to check that these eight numbers sum to $60$ so the average is $\frac {60}{8}=\frac {15}2$ as claimed.
Note: in the problem it is asserted that the number of elements in $S$ is $\varphi(n)+1$ but this is not true (trusting that I understand the notation). Instead, the number is $\varphi(n)$ by definition.