Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
9  
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
show 2 more comments

3 Answers

up vote 3 down vote accepted

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}$.

share|improve this answer
add comment

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}$.

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

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.

share|improve this answer
    
@AsafKaragila: Considered it, sir. –  user63477 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. –  user63477 May 20 '13 at 19:02
    
@AsafKaragila: You are knighted Marshal though.;) –  user63477 May 24 '13 at 7:36
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.