Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

could any one tell me how to find the sum of all positive integers less than $n$ and relatively prime to $n$? $n>1$

For $n=7$, I have $\phi(n)=6$ and the sum is ${6(6+1)\over 2}={n\over 2}.\phi(n)$, is that true for any $n$?

share|cite|improve this question
This would be true for any prime $n$ (like your $7$), since all numbers less than $n$ would in that case be relatively prime. For any other number, not so much. – Arthur Jul 31 '13 at 10:28
up vote 16 down vote accepted

It’s true for all $n>2$. The reason is that if $k\in\{1,\ldots,n-1\}$ is relatively prime to $n$, so is $n-k$, so the integers that you’re adding can be combined into $\frac{\varphi(n)}2$ pairs whose members sum to $n$. If $n>2$, $\frac{n}2$ is never relatively prime to $n$, so you really do get pairs $\{k,n-k\}$.

See OEIS A023896 for some references.

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.