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

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

Completing the proof from @DonAntonio's answer:

Let $$S_n = \sum_{\substack{(k, n) = 1 \\ 0 \leq k \leq n}}{k}$$ Since $(k, n) = (n - k, n)$ we can do a variable substitution as $k = n - k$. Now, $$S_n = \sum_{\substack{(n - k, n) = 1 \\ 0 \leq n - k \leq n}}{n - k} = \sum_{\substack{(k, n) = 1 \\ 0 \leq k \leq n}}{n - k}$$ Adding the two expressions, $$2 \cdot S_n = \sum_{\substack{(k, n) = 1 \\ 0 \leq k \leq n}}{n - k + k} \implies 2 \cdot S_n = \sum_{\substack{(k, n) = 1 \\ 0 \leq k \leq n}}{n} \implies 2 \cdot S_n = n \cdot \phi(n)$$

This is a nice example of where we fully exploit symmetry to compute a sum even though we do not know much about the actual values involved. You can also reach this closed form by first proving that $S_n$ is multiplicative and then breaking $S_n$ into $S_{{p_i}^{\alpha_i}}$ where $p_i$ are factors of $n$. That method is a bit lengthy though.

-