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