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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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
up vote 5 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|cite|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
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.

share|cite|improve this answer

Your Answer


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.