Take the 2-minute tour ×
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.

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

1 Answer 1

up vote 10 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|improve this answer

Your Answer

 
discard

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.