# 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$? [duplicate]

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.

• $6$ is not relatively prime to $3$, so your statement that all even numbers will be relatively prime to $m$ is incorrect. – Anurag A Oct 2 '18 at 22:17

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?

• If we sort the $r_i$ ‘s in ascending order we can add the first and the last element but I don’t know how to pair up the rest of the elements. Also whats the RRS mod 2??? – Pratyush Chopra Oct 3 '18 at 2:15
• @PratyushChopra you don't have to know which specific residues will pair. All you need to observe is that in the list $r_1,r_2, \ldots,r_{\phi(m)}$, for each $r_i$ there exists $r_k$ such that $r_i+r_k \equiv 0 \pmod{m}$. – Anurag A Oct 3 '18 at 5:25
• @PratyushChopra Take an example to better understand the idea. Let $m=9$, then $\{1,2,4,5,7,8\}$ is complete RRS. But we can also write the same system as $\{1,2,4,-4,-2,-1\}$. – Anurag A Oct 3 '18 at 5:27
• I made various examples myself but I still don't know how to prove it for m. And yeah I observed it but how do I show it? – Pratyush Chopra Oct 3 '18 at 11:53

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

• I know that $r_2 + r_{/phi (m)-1}$ is congruent to 0 but I don’t know how to prove it – Pratyush Chopra Oct 3 '18 at 2:13
• If $p\mid a$ and $p\mid a-b$ then this implies $p\mid a-(a-b)=b$. So this tells us $\gcd(a,b)=\gcd(a,a-b)$. Applying this to the RRS, we have $\gcd(m,r_i)=\gcd(m,m-r_i)=1$. Can you take it from here? – Daniel Buck Oct 3 '18 at 2:53