0
$\begingroup$

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.

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

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?

$\endgroup$
  • $\begingroup$ 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??? $\endgroup$ – Pratyush Chopra Oct 3 '18 at 2:15
  • $\begingroup$ @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}$. $\endgroup$ – Anurag A Oct 3 '18 at 5:25
  • $\begingroup$ @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\}$. $\endgroup$ – Anurag A Oct 3 '18 at 5:27
  • $\begingroup$ 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? $\endgroup$ – Pratyush Chopra Oct 3 '18 at 11:53
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I know that $r_2 + r_{/phi (m)-1}$ is congruent to 0 but I don’t know how to prove it $\endgroup$ – Pratyush Chopra Oct 3 '18 at 2:13
  • $\begingroup$ 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? $\endgroup$ – Daniel Buck Oct 3 '18 at 2:53

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