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

  • $\begingroup$ 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. $\endgroup$
    – Arthur
    Jul 31 '13 at 10:28

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.