Exercise 2.1.40 (Sum of the elements of a complete (resp. reduced) residue system)

Proof. Let $\{r_1,r_2,\dots ,r_m\}$ be a complete system modulo $m$, where $m$ is odd, and $S=r_1+r_2+\cdots +r_m$.

a)

First proof. Since $a$ and $m$ are relatively prime, Theorem 2.6 shows that $2r_1,2r_2,\dots ,2r_m$ is a complete system modulo $m$.

Therefore there is a permutation $\sigma \in S_n$ such that

$$2r_i=r_{\sigma (i)},i=1,\dots ,m.$$

Then

$$\begin{array}{llll}\hfill 2S& =2r_1+\cdots +2r_m& \hfill & \\ \hfill & \equiv r_{\sigma (1)}+\cdots +r_{\sigma (m)}(\mathit{mod}m),& \hfill & \\ \hfill & & \hfill \end{array}$$

and $r_{\sigma (1)}+\cdots +r_{\sigma (m)}=S$.

Thus $2S\equiv S(\mathit{mod}m)$, so $S\equiv 0(\mathit{mod}m)$.

Second proof. Since $\{r_1,r_2,\dots ,r_m\}$ be a complete system modulo $m$,

$$\mathbb{Z}∕\mathit{p\mathbb{Z}}=\{[r_1],\dots ,[r_m]\}.$$

where $[a]$ denotes the class of $a\in \mathbb{Z}$ in $\mathbb{Z}∕\mathit{m\mathbb{Z}}$. Thus

$$\begin{array}{llll}\hfill [S]& =\underset{x\in \mathbb{Z}∕\mathit{m\mathbb{Z}}}{\sum }x& \hfill & \\ \hfill & =\underset{i=0}{\overset{m-1}{\sum }}[i]& \hfill & \\ \hfill & =\left[m\left(\frac{m-1}{2}\right)\right](m\text{ is odd.})& \hfill & \\ \hfill & =\left[m\right]\left[\frac{m-1}{2}\right]& \hfill & \\ \hfill & =[0].& \hfill & \end{array}$$

Therefore $S\equiv 0(\mathit{mod}m)$.

Let $\{r_1,\dots ,r_{\varphi (m)}\}$ be a reduced system modulo $m$, where $m>2$, and $S=r_1+\cdots +r_{\varphi (m)}$, so that

The proof of $S\equiv 0(\mathit{mod}m)$ is very different ( $\mathit{aS}\equiv S(\mathit{mod}m)$ doesn’t imply $S\equiv 0(\mathit{mod}m)$).

Here $m>2$, so $m\wedge m=m\ne 1$, and $m∕2\notin {(\mathbb{Z}∕\mathit{m\mathbb{Z}})}^{\text{×}}$ (if $m$ is odd, $m∕2\notin \mathbb{Z}$, and if $m$ is even $(m∕2)\wedge m=m∕2\ne 1$).

Note that

so that we can associate to every element $i$ such that $0<i<m∕2,i\wedge m=1$ the element $m-i$ in the sum $S$. Since $i+(m-i)=m\equiv 0(\mathit{mod}m)$, we obtain $S\equiv 0(\mathit{mod}m)$.

More explicitly,

So, for any reduced system $\{r_1,\dots ,r_{\varphi (m)}\}$, where $m>2$,

□