# How do you prove that the mean of the co-primes of a number is half the number?

Say $n = 6$, The set of co-primes is $\{1, 5\}$, $\text{mean} = 3$

For $n = 9$, the set of co-primes is $\{1, 2, 4, 5, 7, 8 \}, \text{mean} = 4.5$

Question: Prove that the mean of co-primes of $n$, which are less than $n$ is half the number itself.

I computed all values until $10000$ and it seems to hold good.

-
HINT : $(a,n)=(n-a,n)$ –  lab bhattacharjee May 20 '13 at 15:54
Do you mean that if a & n are co-prime, so are n-a & n? –  sureshvv May 20 '13 at 16:00
so you will always have pairs of co-primes that add to the number –  sureshvv May 20 '13 at 16:01
yes. the GCD are same as $d$ divides $a$ and $n\implies d|(n-a)$ and vice versa. –  lab bhattacharjee May 20 '13 at 16:03
i got to the point where i noticed that it was always an even number of co-primes! –  sureshvv May 20 '13 at 16:07

I'm posting a separate answer because I think Inceptio's is far too complicated for a problem this simple.

Note that $a$ is relatively prime to $n$ if and only if $n - a$ is relatively prime to $n$. Also, generally $a \ne n - a$ (though there is one exception, which you have to deal with separately. Can you find the exception?) Anyway, this means we can make a list of everything relatively prime to $n$ in pairs of the form $(a, n - a)$, i.e. our list is: $$a_1, n - a_1, a_2, n - a_2, a_3, n - a_3, \cdots , a_k, n - a_k$$

We can also guarantee that this list is all-inclusive (why?) and that no number appears twice (how?). Then simply add up the numbers in the list and divide by the total. You should get that the average is $\frac{n}{2}$.

-

I assume $n\neq2$. The case $n=2$ should be treated separately (see Goos' comment).

Since $\gcd(a,n)=1\iff\gcd(n-a,n)=1$ it follows that if $C=\{a_1,a_2,\ldots,a_r\}$ is the set of the co-prime positive integers with $n$ (and smaller of $n$) then we can write $$C=\{a_1,a_2,\ldots,a_s,n\color{brown}{-a_s},\ldots,n\color{brown}{-a_2},n\color{brown}{-a_1}\}$$ for $s=\dfrac{r}{2}$.
In your examples for $n=6$, $C=\{1,5\}=\{1,6\color{brown}{-1}\}$ and
for $n=9$, $C=\{1,2,4,5,7,8\}=\{1,2,4,9\color{brown}{-4},9\color{brown}{-2},9\color{brown}{-1}\}$.

Therefore $\sum C=s\cdot n$ and the mean is $\dfrac{\sum C}{2s}=\dfrac{s\cdot n}{2s}=\dfrac{n}{2}$.

-
You forgot to deal with the case $a = n - a$. Trivial, but still should be dealt with. –  Goos May 20 '13 at 18:41

Let $\{a_1, \dots a_{ \phi(n)} \}$ be set of all co-primes of $n$, you notice that $a_{\phi(n)}=n-1( Why?)$ and $a_1=1$.

Let $n= p_1^{\alpha_1} \cdots p_k^{\alpha_j}$ , $p_i \nmid a_k$ where $1 \le i \le k$ and $1 \le j \le \phi(n)$

As rightly noted by Battacharjee in his comment, $\gcd({n,a_i})=1=\gcd(a_i,n-a_i)$

And the proof for that:

$(n,a_i)=d \implies n=df, a=dt \implies \gcd(dt,d(f-t))=d=\gcd(a_i,n)$,since $\gcd(t,f)=1$.

Here $\gcd(a_i, n)=1 \implies \gcd(a_i,n-a_i)=1$

Note that: $a_i, n-a_i \in \{a_1, \dots a_{ \phi(n)} \}$

$$\sum_1^{\phi(n)}a_i= \dfrac{\phi(n) n}{2}$$

Now the result is quite direct.

$$\text{Mean}= \dfrac{\sum_1^{\phi(n)}a_i}{\phi(n)}=\dfrac{n}{2}$$

Some things that need to be explained:

$\phi(n)$ denotes the Totient function. Number of co-primes of $n$ , less than $n$. You should read more about it.

$a_i, n-a_i \in \{a_1, \dots a_{ \phi(n)} \}$(Why?)

Because: $\gcd(a_i, n-a_i)=1$, and all numbers which are co prime to $n$ are in the set, which means they are in the set.

The answer looks too complicated only because of notations. Look at Goos' answer.

-
@AsafKaragila: Considered it, sir. –  Inceptio May 20 '13 at 18:51
I wasn't knighted (so far). –  Asaf Karagila May 20 '13 at 18:55
I think the $\phi$ function should not be introduced for a question this simple, because it does nothing to help the proof. You also give a prime factorization for $n$, but then you don't use it at all :P –  Goos May 20 '13 at 18:57
@Goos: I thought of using the factorization in finding $\phi(n)$, then I thought it was a bad idea. And still the factorization serves little purpose. –  Inceptio May 20 '13 at 19:02
@AsafKaragila: You are knighted Marshal though.;) –  Inceptio May 24 '13 at 7:36