1.21: Residue Classes and the Integers Modelo m

Definition $\PageIndex{1}$

Let $m>0$ be given. For each integer $a$ we define $$\label{eq: [a] defn 1} [a]=\{x:x\equiv a\pmod m\}.$$

In other words, $[a]$ is the set of all integers that are congruent to $a$ modulo $m$. We call $[a]$ the residue class of $a$ modulo $m$. Some people call $[a]$ the congruence class or equivalence class of $a$ modulo $m$.

Example $\PageIndex{1}$

If $m=3$ and $a=7$, we see $$\begin{aligned} \left[7\right] &= \{x:x \equiv 7 \pmod 3\}\\ &= \{\dots, -5, -2, 1, 4, 7, 10, 13, 16, 19, \dots\}. \end{aligned}$$ Keeping $m=3$, we also see that $$\begin{aligned} \left[0\right] &= \{x:x \equiv 0 \pmod 3\}\\ &= \{\dots, -9, -6, -3, 0, 3, 6, 9, \dots\};\\[6pt] [1] &= \{x:x \equiv 1 \pmod 3\}\\ &= \{\dots, -8, -5, -2, 1, 4, 7, 10, \dots\};\\[6pt] [2] &= \{x:x \equiv 2 \pmod 3\}\\ &= \{\dots, -7, -4, -1, 2, 5, 8, 11, \dots\}. \end{aligned}$$ So every integer belongs to one of the residue classes modulo 3. Note also that $[7]=[1]$, since $[7]$ and $[1]$ are both sets containing exactly the same elements; think of $[7]$ and $[1]$ as different names for the same set. (With this perspective, each residue class has infinitely many names.)

Theorem $\PageIndex{1}$

For $m>0$ and any integer $a$ we have $$\label{eq: [a] defn 2} [a]=\{mq+a\mid q\in\mathbb{Z}\}.$$

Proof

$x\in[a]\Leftrightarrow x\equiv a\pmod m\Leftrightarrow m\mid (x-a)\Leftrightarrow x-a=mq$ for some $q\in\mathbb{Z}\Leftrightarrow x=mq+a$ for some $q\in\mathbb{Z}$. So equation $\eqref{eq: [a] defn 2}$ follows from the definition in equation $\eqref{eq: [a] defn 1}$.

Note that $[a]$ really depends on $m$ and it would be more accurate to write $[a]_m$ instead of $[a]$, but this would be too cumbersome. Nevertheless it should be kept clearly in mind that $[a]$ depends on some understood value of $m$.

Remark $\PageIndex{1}$

Two alternative ways to write equation $\eqref{eq: [a] defn 2}$ are $$[a]=\{mq+a\mid q=0,\pm 1,\pm 2,\dotsc\}\nonumber$$ and $$[a]=\{\dotsc,-2m+a,-m+a,a,m+a,2m+a,\dotsc\}.\nonumber$$

Theorem $\PageIndex{2}$

For a given modulus $m>0$ we have: $$[a]=[b]\Leftrightarrow a\equiv b\pmod m.\nonumber$$

Proof

“$\Rightarrow$” Assume $[a]=[b]$. Note that since $a\equiv a\pmod m$ we have $a\in[a]$. Since $[a]=[b]$ we have $a\in[b]$. By definition of $[b]$ this gives $a\equiv b\pmod m$, as desired.

“$\Leftarrow$” Assume $a\equiv b\pmod m$. We must prove that the sets $[a]$ and $[b]$ are equal. To do this we prove that every element of $[a]$ is in $[b]$ and vice-versa. Let $x\in[a]$. Then $x\equiv a\pmod m$. Since $a\equiv b\pmod m$, by transitivity $x\equiv b\pmod m$ so $x\in[b]$. Conversely, if $x\in[b]$, then $x\equiv b\pmod m$. By symmetry since $a\equiv b\pmod m$, $b\equiv a\pmod m$, so again by transitivity $x\equiv a\pmod m$ and $x\in[a]$. This proves that $[a]=[b]$.

Theorem $\PageIndex{3}$

For every $a$ there is a unique $r$ such that $$[a]=[r]\quad \mbox{and $0\le r<m$}.\nonumber$$

Proof

Let $r=a\bmod m$. Then by Theorem 1.17.2 (1) we have $a\equiv r\pmod m$. By definition of $a\bmod m$ we have $0\le r<m$. Since $a\equiv r\pmod m$ by Theorem $\PageIndex{2}$, $[a]=[r]$. To prove that $r$ is unique, suppose also $[a]=[r']$ where $0\le r'<m$. By Theorem $\PageIndex{2}$ this implies that $a\equiv r'\pmod m$. This, together with $0\le r'<m$, implies by Theorem 1.17.4 that $r'=a\bmod m=r$.

Theorem $\PageIndex{4}$

Given $m>0$, there are exactly $m$ distinct residue classes modulo $m$, namely, $$[0],[1],[2],\dotsc,[m-1].\nonumber$$

Proof

By Theorem $\PageIndex{3}$ we know that every residue class $[a]$ is equal to one of the residue classes: $[0],[1],\dotsc,[m-1]$. So there are no residue classes not in this list. These residue classes are distinct by the uniqueness part of Theorem $\PageIndex{3}$, namely if $0\le r_1<m$ and $0\le r_2<m$ and $[r_1]=[r_2]$, then by the uniqueness part of Theorem $\PageIndex{3}$ we must have $r_1=r_2$.

Definition $\PageIndex{2}$: Representative

Any element $x\in[a]$ is said to be a representative of the residue class $[a]$.

As you are asked to show in Exercise $\PageIndex{4}$ below, if $x$ is a representative of $[a]$ then $[x]=[a]$, that is, any element of a residue class may be used to represent it.

The integers modulo $m$

Henceforth in this chapter let $m$ be a fixed integer that is greater than 1.

Definition $\PageIndex{3}$: Ring of Integers Modulo m

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 C for the definition of ring.) Often we drop “the ring of” and just call $\mathbb{Z}_m$ the integers modulo $m$. From Theorem $\PageIndex{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.$^{1}$ By Exercise $\PageIndex{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{2}$

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

We now show how to define addition and multiplication of residue classes modulo $m$. It is with respect to these binary operations that $\mathbb{Z}_m$ is a ring (again, see Appendix C).

Definition $\PageIndex{4}$

For $[a],[b]\in\mathbb{Z}_m$ we define $$[a]+[b]=[a+b]\nonumber$$ and $$[a][b]=[ab].\nonumber$$

Example $\PageIndex{3}$

For $m=5$ we have $$[2]+[3]=[5],\nonumber$$ and $$[2][3]=[6].\nonumber$$ Note that since $5\equiv 0\pmod 5$ and $6\equiv 1\pmod 5$ we have $[5]=[0]$ and $[6]=[1]$ so we can also write $$\begin{gathered} \left[2\right]+[3]=[0] \\ [2][3]=[1].\end{gathered}$$

Since a residue class can have many representatives, it is important to check that the rules given in Definition $\PageIndex{4}$ do not depend on the representatives chosen. For example, when $m=5$ we know that $$[7]=[2]\text{ and }[11]=[21]\nonumber$$ so we should have $$[7]+[11]=[2]+[21]\nonumber$$ and $$[7][11]=[2][21].\nonumber$$ In this case we can check that $$[7]+[11]=[18]\text{ and }[2]+[21]=[23].\nonumber$$ Now $23\equiv 18\pmod 5$ since $5\mid (23-18)$. Hence $[18]=[23]$, as desired. Also $[7][11]=[77]$ and $[2][21]=[42]$. Then $77-42=35$ and $5\mid 35$ so $77\equiv 42\pmod 5$ and hence $[77]=[42]$, as desired.

Theorem $\PageIndex{5}$

For any modulus $m>0$ if $[a]=[b]$ and $[c]=[d]$ then $$[a]+[c]=[b]+[d]\nonumber$$ and $$[a][c]=[b][d].\nonumber$$

Proof

See Exercise $\PageIndex{8}$ below.

When performing addition and multiplication in $\mathbb{Z}_m$ using the rules in Definition $\PageIndex{4}$, due to Theorem $\PageIndex{5}$, we may at any time replace $[a]$ by $[a']$ if $a\equiv a'\pmod m$. This will sometimes make calculations easier.

Example $\PageIndex{4}$

Take $m=151$. Then $150\equiv-1\pmod{151}$ and $149\equiv-2\pmod{151}$, so $$[150][149]=[-1][-2]=[2]\nonumber$$ and $$[150]+[149]=[-1]+[-2]=[-3]=[148]\nonumber$$ since $148\equiv-3\pmod{151}$.

When working with $\mathbb{Z}_m$ it is often useful to write each residue class using its name $[a]$, where $a$ is the least nonnegative number in the set. We do this in constructing the following addition and multiplication tables for $\mathbb{Z}_4$. For example, $[2]\cdot[3] = [6]$, but since $[6] = [2]$ and $2$ is the smallest nonnegative member of this set, the table records $[2]\cdot [3] = [2]$.

$+$	$[0]$	$[1]$	$[2]$	$[3]$
$[0]$	$[0]$	$[1]$	$[2]$	$[3]$
$[1]$	$[1]$	$[2]$	$[3]$	$[0]$
$[2]$	$[2]$	$[3]$	$[0]$	$[1]$
$[3]$	$[3]$	$[0]$	$[1]$	$[2]$

$\cdot$	$[0]$	$[1]$	$[2]$	$[3]$
$[0]$	$[0]$	$[0]$	$[0]$	$[0]$
$[1]$	$[0]$	$[1]$	$[2]$	$[3]$
$[2]$	$[0]$	$[2]$	$[0]$	$[2]$
$[3]$	$[0]$	$[3]$	$[2]$	$[1]$

Recall that by Theorem 1.17.2 (1) we have for all $a$ and $m>0$ $$a\equiv a\bmod m\pmod m.\nonumber$$ So using residue classes modulo $m$ this gives $$[a]=[a\bmod m].\nonumber$$

Hence, $$\boxed{\begin{array}{c}[a]+[b]=[(a+b)\bmod m] \\ [a][b]=[(ab)\bmod m]\end{array}}\nonumber$$

So if $a$ and $b$ are in the set $\{0,1,\dotsc,m-1\}$, these equations give us a way to obtain representations of the sum and product of $[a]$ and $[b]$ using “names” (representatives) also in $\{0,1,\dotsc,m-1\}$. This leads to an alternative way to define $\mathbb{Z}_m$ and addition and multiplication in $\mathbb{Z}_m$. We will use slightly different notation.

Definition $\PageIndex{5}$

For $m>0$ define $$Z_m=\{0,1,2,\dotsc,m-1\}\nonumber$$ and for $a,b\in Z_m$ $$\begin{aligned} a+b &=(a+b)\bmod m \\ ab &=(ab)\bmod m.\end{aligned}$$ where the addition and multiplication inside the parentheses are the usual addition and multiplication of integers; what is new in our redefinition is the practice of always reducing the result modulo $m$.

Remark $\PageIndex{2}$

The set $Z_m$ with addition and multiplication as defined is isomorphic to $\mathbb{Z}_m$ with addition and multiplication given by Definition $\PageIndex{4}$. (Students taking a course in elementary abstract algebra will learn a rigorous definition of the term isomorphic. For now, we take “isomorphic” to mean “has the same form.”) The addition and multiplication tables for $Z_4$ are here:

$+$	$0$	$1$	$2$	$3$
$0$	$0$	$1$	$2$	$3$
$1$	$1$	$2$	$3$	$0$
$2$	$2$	$3$	$0$	$1$
$3$	$3$	$0$	$1$	$2$

	$0$	$1$	$2$	$3$
$0$	$0$	$0$	$0$	$0$
$1$	$0$	$1$	$2$	$3$
$2$	$0$	$2$	$0$	$2$
$3$	$0$	$3$	$2$	$1$

Example $\PageIndex{5}$

Let’s solve the congruence $$272x\equiv 901\pmod 9.\nonumber$$ Using residue classes modulo $9$, this congruence is equivalent to $$[272x]=[901],\nonumber$$ which is equivalent to $$[272][x]=[901],\nonumber$$ which is equivalent to $$[2][x]=[1].\nonumber$$ Now we know $[x]\in\{[0],[1],\dotsc,[8]\}$ so by trial and error we see that $x=5$ is a solution; actually, every integer in the residue class $[5]$ is a solution.

Exercises

Exercise $\PageIndex{1}$

Show that if $m=2$ then $[1]$ is the set of all odd integers and $[0]$ is the set of all even integers. Show also that $\mathbb{Z} = [0] \cup [1]$ and $[0] \cap [1] = \emptyset$.

Exercise $\PageIndex{2}$

Show that if $m=3$, then $[0]$ is the set of integers divisible by $3$, $[1]$ is the set of integers whose remainder when divided by $3$ is $1$, and $[2]$ is the set of integers whose remainder when divided by $3$ is $2$. Show also that $\mathbb{Z} = [0] \cup [1] \cup [2]$ and $[0] \cap [1] = [0] \cap [2] = [1] \cap [2] =\emptyset$.

Exercise $\PageIndex{3}$

Given the modulus $m>0$ show that $[a]=[a+m]$ and $[a]=[a-m]$ for all $a$.

Exercise $\PageIndex{4}$

For any $m>0$, show that if $x\in[a]$ then $[a]=[x]$.

Exercise $\PageIndex{5}$

For any $m>0$, show that if $[a]\cap[b]\ne\emptyset$ then $[a]=[b]$.

Exercise $\PageIndex{6}$

For any $m>0$, show that if $[a]\ne[b]$ then $[a]\cap[b]=\emptyset$.

Exercise $\PageIndex{7}$

Let $m=2$. Show that $$[0]=[2]=[4]=[32]=[-2]=[-32]\nonumber$$ and $$[1]=[3]=[-3]=[31]=[-31].\nonumber$$

Exercise $\PageIndex{8}$

Prove Theorem $\PageIndex{5}$.

(Hint: Use Theorems 1.17.3 and $\PageIndex{2}$.)

Exercise $\PageIndex{9}$

Construct addition and multiplication tables for $Z_5$.

Exercise $\PageIndex{10}$

Without doing it, tell how to obtain addition and multiplication tables for $\mathbb{Z}_5$ from the work in Exercise $\PageIndex{9}$.

Exercise $\PageIndex{11}$

1. If $p$ is a prime, show that $x^2 \equiv 1 \pmod p$ if and only if $x \equiv -1 \pmod p$ or $x \equiv 1 \pmod p$. (Hint: as part of your answer, explain why $x^2 \equiv 1 \pmod p$ implies that $p | (x+1)(x-1)$ and apply Euclid’s Lemma (Lemma 1.11.2).
2. Conclude that, modulo a prime $p$, the congruence $[x]^2 = [1]$ has solutions $[x]=[1]$ and $[x] = [-1]$.
3. Find an example of a modulus $m$ and a residue class $[a]$ such that $[a]^2 = [1]$ but $[a]\neq [1]$ and $[a]\neq [-1]$ in $\mathbb{Z}_m$.

Exercise $\PageIndex{12}$

Solve the congruence $544x \equiv 863 \pmod 7$.

Footnotes

[1] Each of those elements, like $[0]$ or $[1]$, is itself a set with infinitely many elements, but we will often ignore this. The $m$ sets $[0],\: [1],\cdots , [m- 1]$ in $\mathbb{Z}_m$ are its $m$ elements.