1.19: Residue Classes

Definition \(\PageIndex{1}\)

Let \(m>0\) be given. For each integer \(a\) we define \[\label{eq: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\).

Theorem \(\PageIndex{1}\)

For \(m>0\) we have \[\label{eq: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 \(\eqref{eq:2}\) follows from the definition \(\eqref{eq: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 \(\eqref{eq:2}\) are \[\label{eq:3} [a] =\{mq+a\mid q=0,\pm 1,\pm 2,\dotsc\} \] or \[\label{eq:4} [a] =\{\dotsc,-2m+a,-m+a,a,m+a,2m+a,\dotsc\}. \]

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\).

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}\)

Given \(m>0\). 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 Exercise 15.1 we have \(a\equiv r\pmod m\). By definiton 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 15.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\).

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]\).

Definition \(\PageIndex{2}\)

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

By Exercise \(\PageIndex{4}\) if \(x\) is a representative of \([a]\) then \([x]=[a]\), that is, any element of a residue class may be used to represent it.

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\]