1.20: Zm and Complete Residue Systems

Throughout this section we assume a fixed modulus $m>0$.

Definition $\PageIndex{1}$

We define $$\mathbb{Z}_m=\{[a]\mid a\in\mathbb{Z}\},\nonumber$$ that is, $\mathbb{Z}_m$ is the set of all residue classes modulo $m$. We call $\mathbb{Z}_m$ the ring of integers modulo $m$. In the next chapter we shall show how to add and multiply residue classes. This makes $\mathbb{Z}_m$ into a ring. See Appendix A for the definition of ring. Often we drop the ring and just call $\mathbb{Z}_m$ the integers modulo $m$. From Theorem 19.4 $$\mathbb{Z}_m=\{[0],[1],\dotsc,[m-1]\}\nonumber$$ and since no two of the residue classes $[0],[1],\dotsc,[m-1]$ are equal we see that $\mathbb{Z}_m$ has exactly $m$ elements. By Exercise 19.4 if we choose $$a_0\in[0],a_1\in[1],\dotsc,a_{m-1}\in[m-1]\nonumber$$ then $$[a_0]=[0],[a_1]=[1],\dotsc,[a_{m-1}]=[m-1].\nonumber$$ So we also have $$\mathbb{Z}_m=\{[a_0],[a_1],\dotsc,[a_{m-1}]\}.\nonumber$$

Example $\PageIndex{1}$

If $m=4$ we have, for example, $$8\in [0], 5 \in [1], -6 \in [2], 11\in [3].\nonumber$$ And hence: $$\mathbb{Z}_4 = \{[8],[5],[-6],[11] \}.\nonumber$$

Definition $\PageIndex{2}$

A set of $m$ integers $$\{a_0,a_1,\dotsc,a_{m-1}\}\nonumber$$ is called a complete residue system modulo $m$ if $$\mathbb{Z}_m=\{[a_0],[a_1],\dotsc,[a_{m-1}]\}.\nonumber$$

Remark $\PageIndex{1}$

A complete residue system modulo $m$ is sometimes called a complete set of representatives for $\mathbb{Z}_m$.

Example $\PageIndex{2}$

By Theorem 19.4, for $m>0$ $$\{0,1,2,\dotsc,m-1\}\nonumber$$ is a complete residue system modulo $m$.

Example $\PageIndex{3}$

From the above discussion it is clear that for each $m > 0$ there are infinitely many distinct complete residue systems modulo $m$. For example, here are some examples of complete residue systems modulo 5:

1. $\{0,1,2,3,4\}$
2. $\{0,1,2,-2,-1\}$
3. $\{10,-9,12,8,14\}$
4. $\{0+5n_1,1+5n_2,2+5n_3,3+5n_4,4+5n_4 \}$ where $n_1,n_2,n_3,n_4,n_5$ may be any integers.

Definition $\PageIndex{3}$

The set $\{0,1,\dotsc,m-1\}$ is called the set of least nonnegative residues modulo $m$.

Theorem $\PageIndex{1}$

Let $m>0$ be given.

1. If $m=2k$, then $$\{0,1,2,\dotsc,k-1,k,-(k-1),\dotsc,-2,-1\}\nonumber$$ is a complete residue system modulo $m$.
2. If $m=2k+1$, then $$\{0,1,2,\dotsc,k,-k,\dotsc,-2,-1\}\nonumber$$ is a complete residue system modulo $m$.

Proof

Proof of (1). Since if $m=2k$ $$\mathbb{Z}_m=\{[0],[1],\dotsc,[k],[k+1],\dotsc,[k+i],[k+k-1]\},\nonumber$$ it suffices to note that by Exercise 19.3 we have $$[k+i]=[k+i-2k]=[-k+i]=[-(k-i)].\nonumber$$ So $$[k+1]=[-(k-1)],[k+2]=[-(k-2)],\dotsc,[k+k-1]=[-1],\nonumber$$ as desired.

Proof of (2). In this case $$[k+i]=[-(2k+1)+k+i]=[-k+i+1]=[-(k-i+1)]\nonumber$$ so $$[k+1]=[-k],[k+2]=[-(k-1)],\dotsc,[2k]=[-1],\nonumber$$ as desired.

Definition $\PageIndex{4}$

The complete residue system modulo $m$ given in Theorem $\PageIndex{1}$ is called the least absolute residue system modulo $m$.

Remark $\PageIndex{2}$

If one chooses in each residue class $[a]$ the smallest nonnegative integer one obtains the least nonnegative residue system. If one chooses in each residue class $[a]$ an element of smallest possible absolute value one obtains the least absolute residue system.

Exercise $\PageIndex{1}$

Find both the least nonnegative residue system and the least absolute residues for each of the moduli given below. Also, in each case find a third complete residue system different from these two. $$m=3,\quad m=4,\quad m=5,\quad m=6,\quad m=7,\quad m=8.\nonumber$$