If $m > 0$, fix a reduced residue system $r_{1}, r_2, \dotsc, r_{\varphi(m)} $ mod $ m$. Let $x=r_1+r_2+\dotsb+r_{\varphi(m)}$. What is $x$ mod $m$?

Question

Given $m > 0$, fix a reduced residue system (RRS) $r_{1}, r_2,\dotsc , r_{\varphi(m)} $ mod $ m$. Let $x$ denote the sum $r_1 + r_2 + \dotsb + r_{\varphi(m)}$. What is $x$ mod $m$?

The problem is that I'm stuck. So suppose that $m = 2k + 1$. Then the RRS would include an even number of elements since all even numbers are relatively prime to $m$. But I don't know what to do with this information and I also don't know how to solve for if $m$ is even. Any help will be appreciated.

Answer 1

Hint:

If $r_i$ is a reduced residue modulo $m$, then so is $-r_i$. Moreover $\phi(m)$ is even for $m \geq 3$. So can you pair things up in the sum?

Answer 2

Let the reduced residue system $r_{1}, r_2, \dotsc , r_{\varphi(m)}\pmod m$ be in ascending order.

Note: $r_1=1$, $r_{\varphi(m)}=m-1\equiv-1\pmod{m}$, then $r_1+r_{\varphi(m)}\equiv0\pmod{m}$.

Now what can be said of $r_2$ and $r_{\varphi(m)-1}$?

Note: $\varphi(m)=m\prod_{p_i}\left(1-\frac1{p_i}\right)$, and is even for $m\ge3$.