1
$\begingroup$

Prove that sum of elements in reduced residue system modulo $n \in N$ is divisible by $n$.

I feel like problem just comes down to pairing elements of RRS in way that they are congruent, but can't quite work it out. Please post detailed and readable answer, as most of problems I need to do basically comes down to this one ..

$\endgroup$
  • $\begingroup$ Not true for even $n$. $\endgroup$ – Robert Israel Dec 18 '18 at 16:23
  • 1
    $\begingroup$ Really ? What's your counterexample ? $\endgroup$ – user626177 Dec 18 '18 at 16:43
  • 1
    $\begingroup$ @someone what about $2$? $\endgroup$ – Maged Saeed Dec 18 '18 at 17:45
  • 1
    $\begingroup$ @MagedSaeed Is it working for $n \ne 2$ ? $\endgroup$ – user626177 Dec 18 '18 at 17:57
  • $\begingroup$ @someone consider my answer for other values of $n$. :) $\endgroup$ – Maged Saeed Dec 18 '18 at 18:19
0
$\begingroup$

The reduced residue system of $2$ is only $1$. But $2\not | 1$, so, $n > 2$.

Let us address this problem for numbers greater than $2$. Now, since $\gcd(a,n) = 1$, what can you say about $\gcd(n-a,n)$? It is also $1$. Now, we can use this to pair elements of the Reduced Residue System, as you have suggested, as follows:

$a_1+a_2+a_3+\cdots+a_{\phi(n)\over2}+(n-a_1)+(n-a_2)+\cdots+(n-a_{\phi(n)\over2}) = \frac{\phi(n)}{2}n$. This also can give you a hint why $2$ is a counter example as $\phi(n)$ is only odd for $n=2$. This answer is collected from answers in this post.

$\endgroup$
  • 1
    $\begingroup$ Ooh, right .. So if $k \in RRS$ then $n-k \in RRS$ because $(n-k, n) = 1$ and $n-k \ne k mod n$ ? $\endgroup$ – user626177 Dec 18 '18 at 18:32
  • 1
    $\begingroup$ Yeah, you got it. $\endgroup$ – Maged Saeed Dec 18 '18 at 18:37