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.

What is the sum of all coprimes to number less than that number?
I found a bit about it: For example we have to find the sum of coprimes of 2016. Therefore, the required sum $S$ is:
$2016 = 2^5 * 7 * 3^2$
$S = \frac{2016}2 * 2016 * (1-\frac13)(1-\frac17)(1-\frac12) = 580608$
If this is right, then the formula should be $S = \frac{N^2}2 * (1-\frac1{\text{prime factor 1}})* (1-\frac1{\text{prime factor 2}})...$
If this example and the interpreted formula is right, then how do I prove it? If this is wrong, then what is the actual formula and its proof?

share|improve this question
1  
    
It says that $S = \frac{n}2.\phi(n)$. What is $\phi(n)$? –  shaurya gupta Nov 16 '13 at 14:10
1  
$$n\phi(n)= \prod p^P p^{P-1}(p-1)=\prod p^2 \left(1-\frac1p\right)=\cdots $$ –  lab bhattacharjee Nov 16 '13 at 14:12
add comment

1 Answer 1

up vote 2 down vote accepted

Yes, the formula is right and if you reached it by yourself it is remarkable. If $\;\phi(n)\;$ is Euler's Totient Function, then the sum you want is

$$\frac n2\phi(n)=\frac{n^2}2\prod_{p\mid n\,,\,p\,\text{a prime}}\left(1-\frac1p\right)$$

Hint for the proof: $\;1\le k <n\;$ is coprime to $\;n\;$ iff $\;n-k\;$ is also coprime with $\;n\;$ ...

share|improve this answer
    
Honestly, I never reached it by myself. –  shaurya gupta Nov 16 '13 at 14:32
    
How do I use the Hint for proving the formula? –  shaurya gupta Nov 16 '13 at 14:33
1  
How many pairs $\;\{k\,,\,n-k\}\;,\,\,(n,k)=(n,n-k)=1\;$ do you have ? You may also want to check when $\;2k=n\;$ ... –  DonAntonio Nov 16 '13 at 14:42
    
The difficulty is not in counting how many coprime numbers there are (read about the $\phi$ function mentioned), but in determining which values they have in order to sum them up. By showing there is a symmetry to them you can determine their average value without knowing exactly which numbers they are. –  half-integer fan Nov 16 '13 at 14:50
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.