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.