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$?
Elementary Number Theory – Sum of All Positive Integers Less Than $n$ and Relatively Prime to $n$
elementary-number-theory
Best Answer
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.