# sum of all coprimes of a number.

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?

-
It says that $S = \frac{n}2.\phi(n)$. What is $\phi(n)$? –  shaurya gupta Nov 16 '13 at 14:10
$$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

## 1 Answer

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\;$ ...

-
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
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