6.3 Combining congruence classes

In the previous section we saw that ‘‘congruence modulo $5$’’ is an example of an equivalence relation on the set $\mathbb{Z}$; there are $5$ congruence classes, $\widehat{0}$, $\widehat{1}$, $\widehat{2}$, $\widehat{3}$ and $\widehat{4}$, which partition $\mathbb{Z}$, meaning that every integer lies in exactly one of these classes. (Of course, there is nothing special about the natural number $5$ here.) In this section we shall see that it is possible to give the collection of these classes an arithmetic, which in many ways is similar to the ordinary arithmetic of the integers themselves, but has the advantage of being much simpler; using it we shall be able to answer some apparently difficult questions very easily.

We start with a piece of notation.

Thus $\mathbb{Z}_{m}=\{\widehat{0},\widehat{1},\dots,\widehat{m-1}\}$. Our goal is to decide how to equip the set $\mathbb{Z}_{m}$ with an addition and a multiplication.

We begin with addition, and for definiteness work in $\mathbb{Z}_{5}$; this means that we need, for example, to define the sum of $\widehat{1}$ and $\widehat{2}$. Since $1+2=3$, the obvious thing to do is to set this to be $\widehat{3}$; but we have to be rather careful here, for the following reason. What we seem to be doing is taking two representative elements of the classes $\widehat{1}$ and $\widehat{2}$, adding the elements and then taking the class containing the sum. However, the integer $1$ is only one of many representatives of the class $\widehat{1}$; likewise with the representative $2$ of the class $\widehat{2}$. If we had chosen other representatives, is it conceivable that we might have ended up with a different class for the sum? For example, we could instead have chosen representatives $11$ of $\widehat{1}$ and $7$ of $\widehat{2}$; then we would have calculated $11+7=18$ and obtained the class $\widehat{18}$ as the sum. Since $\widehat{18}=\widehat{3}$, in this case the answer is in fact the same; but we need to be sure that it will always be the same, no matter which representatives are chosen.

To make the point that this is not obvious, let us first consider a situation where things do not work properly. Continue to work in $\mathbb{Z}_{5}$, but instead of addition let us attempt to define taking powers; given $\widehat{a},\widehat{b}\in\mathbb{Z}_{5}$, can we define $\widehat{a}\,^{\widehat{b}}$ as the class containing $a^{b}$? Let $a=2$ and $b=1$. If we take the representatives $2\in\widehat{a}$ and $1\in\widehat{b}$, then we have $\widehat{2^{1}}=\widehat{2}$. However, if instead we had taken the representative $6\in\widehat{b}$ (and still $2\in\widehat{a}$), then we would have got $\widehat{2^{6}}=\widehat{64}=\widehat{4}$. Now $\widehat{2}\neq\widehat{4}$; so taking different representatives changes the final class, and we cannot define $\widehat{a}\,^{\widehat{b}}$ in this way.

So there genuinely is something to be shown if our attempt to define addition is to work. Of course, we do not want to have to do lots of checks like that above (we would in fact need to do infinitely many!). Instead we require a general result, which generalizes Lemma 5.1.7.

Proof. Take $q,r\in\mathbb{Z}$ such that $a=qm+c$ and $b=rm+d$. Then we have

$$a+b=(qm+c)+(rm+d)=(q+r)m+(c+d),$$

so that $a+b\equiv c+d\bmod m$. Moreover,

$$ab=(qm+c)(rm+d)=(qrm+qd+cr)m+cd,$$

so that $ab\equiv cd\bmod m$, and finally

$$-a=-(qm+c)=(-q)m+(-c),$$

so that $-a\equiv-c\bmod m$. $\Box$

Lemma 6.3.2 enables us to make the following definition without any ambiguity.

Our ‘‘new’’ addition and multiplication inherit many properties from the ordinary versions; for example, for all $a,b\in\mathbb{Z}$ we have $a+b=b+a$ and $ab=ba$, and therefore

$$\widehat{a}+\widehat{b}=\widehat{a+b}=\widehat{b+a}=\widehat{b}+\widehat{a}\qquad\hbox{and}\qquad\widehat{a}\cdot\widehat{b}=\widehat{ab}=\widehat{ba}=\widehat{b}\cdot\widehat{a}.$$

Moreover, our system also has subtraction: in $\mathbb{Z}$ we may regard $a-b$ as $a+(-b)$, so in $\mathbb{Z}_{m}$ we set $\widehat{a}-\widehat{b}=\widehat{a}+(-\widehat{b})=\widehat{a}+\widehat{-b}=\widehat{a-b}$ as expected. (As in $\mathbb{Z}$, however, division is another matter.)

Since the set $\mathbb{Z}_{m}$ is finite, we may give addition and multiplication tables listing the results of combining any two classes. In $\mathbb{Z}_{5}$, for example, we obtain the following.

$$\begin{array}[]{|c|ccccc|}\hline+&\widehat{0}&\widehat{1}&\widehat{2}&\widehat{3}&\widehat{4}\\ \hline\widehat{0}&\widehat{0}&\widehat{1}&\widehat{2}&\widehat{3}&\widehat{4}\\ \widehat{1}&\widehat{1}&\widehat{2}&\widehat{3}&\widehat{4}&\widehat{0}\\ \widehat{2}&\widehat{2}&\widehat{3}&\widehat{4}&\widehat{0}&\widehat{1}\\ \widehat{3}&\widehat{3}&\widehat{4}&\widehat{0}&\widehat{1}&\widehat{2}\\ \widehat{4}&\widehat{4}&\widehat{0}&\widehat{1}&\widehat{2}&\widehat{3}\\ \hline\end{array}\qquad\qquad\begin{array}[]{|c|ccccc|}\hline\times&\widehat{0}&\widehat{1}&\widehat{2}&\widehat{3}&\widehat{4}\\ \hline\widehat{0}&\widehat{0}&\widehat{0}&\widehat{0}&\widehat{0}&\widehat{0}\\ \widehat{1}&\widehat{0}&\widehat{1}&\widehat{2}&\widehat{3}&\widehat{4}\\ \widehat{2}&\widehat{0}&\widehat{2}&\widehat{4}&\widehat{1}&\widehat{3}\\ \widehat{3}&\widehat{0}&\widehat{3}&\widehat{1}&\widehat{4}&\widehat{2}\\ \widehat{4}&\widehat{0}&\widehat{4}&\widehat{3}&\widehat{2}&\widehat{1}\\ \hline\end{array}$$

In $\mathbb{Z}_{4}$ we obtain instead these tables.

$$\begin{array}[]{|c|cccc|}\hline+&\widehat{0}&\widehat{1}&\widehat{2}&\widehat{3}\\ \hline\widehat{0}&\widehat{0}&\widehat{1}&\widehat{2}&\widehat{3}\\ \widehat{1}&\widehat{1}&\widehat{2}&\widehat{3}&\widehat{0}\\ \widehat{2}&\widehat{2}&\widehat{3}&\widehat{0}&\widehat{1}\\ \widehat{3}&\widehat{3}&\widehat{0}&\widehat{1}&\widehat{2}\\ \hline\end{array}\qquad\qquad\begin{array}[]{|c|cccc|}\hline\times&\widehat{0}&\widehat{1}&\widehat{2}&\widehat{3}\\ \hline\widehat{0}&\widehat{0}&\widehat{0}&\widehat{0}&\widehat{0}\\ \widehat{1}&\widehat{0}&\widehat{1}&\widehat{2}&\widehat{3}\\ \widehat{2}&\widehat{0}&\widehat{2}&\widehat{0}&\widehat{2}\\ \widehat{3}&\widehat{0}&\widehat{3}&\widehat{2}&\widehat{1}\\ \hline\end{array}$$

Lemma 6.3.2 shows that if $a\equiv b\bmod m$ then $a^{2}\equiv b^{2}\bmod m$; so we have the concept of ‘‘squares modulo $m$’’. The following result is easy.

Proof. Let $n\in\mathbb{Z}$ be given. Since each integer is congruent to either $0$, $1$, $2$ or $3$ modulo $4$, there are four cases to consider:

• •

  if $n\equiv 0\bmod 4$, then $n^{2}\equiv 0^{2}=0\bmod 4$;
  

• •

  if $n\equiv 1\bmod 4$, then $n^{2}\equiv 1^{2}=1\bmod 4$;
  

• •

  if $n\equiv 2\bmod 4$, then $n^{2}\equiv 2^{2}=4\equiv 0\bmod 4$;
  

• •

  otherwise $n\equiv 3\bmod 4$, and $n^{2}\equiv 3^{2}=9\equiv 1\bmod 4$. $\Box$

Note that this result can be read from the main diagonal of the multiplication table in $\mathbb{Z}_{4}$ given above.

Proof. We shall prove the statement by contraposition. To do so, we begin by expressing it symbolically; it can be rewritten as ‘‘$p\Rightarrow(\neg q)$’’, where

$$p\colon\quad n\equiv 3\bmod 4\qquad\text{and}\qquad q\colon\quad(\exists\,a,b\in\mathbb{Z})(n=a^{2}+b^{2}).$$

Recall from Example 2.3.7 that the law of contraposition implies that the statement ‘‘$p\Rightarrow(\neg q)$’’ is logically equivalent to ‘‘$\bigl(\neg(\neg q)\bigr)\Rightarrow(\neg p)$’’, that is, ‘‘$q\Rightarrow(\neg p)$’’.

To prove this final statement, suppose that $q$ is true, so that $n=a^{2}+b^{2}$ for some $a,b\in\mathbb{Z}$. By Proposition 6.3.5, $a^{2}$ and $b^{2}$ are congruent to either $0$ or $1$ modulo $4$, so there are four cases to consider:

• •

  if $a^{2}\equiv 0$ and $b^{2}\equiv 0\bmod 4$, then $n=a^{2}+b^{2}\equiv 0+0=0\not\equiv 3\bmod 4$;
  

• •

  if $a^{2}\equiv 0$ and $b^{2}\equiv 1\bmod 4$, then $n=a^{2}+b^{2}\equiv 0+1=1\not\equiv 3\bmod 4$; the case where $a^{2}\equiv 1$ and $b^{2}\equiv 0\bmod 4$ is similar;
  

• •

  if $a^{2}\equiv 1$ and $b^{2}\equiv 1\bmod 4$, then $n=a^{2}+b^{2}\equiv 1+1=2\not\equiv 3\bmod 4$.

Hence in each case $n\;\not\equiv 3\bmod 4$, so $p$ is never satisfied, and the result follows. $\Box$

Our observation above about taking squares modulo $m$ extends to cubes or indeed any powers: if $a\equiv b\bmod m$ then $a^{n}\equiv b^{n}\bmod m$ for any $n\in\mathbb{N}$. (Do not confuse this with the remarks earlier about the impossibility of defining $\widehat{a}\,^{\widehat{b}}$ for classes $\widehat{a}$ and $\widehat{b}$; there we were attempting to raise one class to the power of another class, whereas what is being claimed here is simply that it makes sense to raise a class to a given power.)

This result enables us to simplify certain expressions when working modulo $m$.

Note: this means ‘‘find $x\in\{0,1,2,\ldots,14\}$ such that $2^{27}\equiv x\bmod 15$’’.

Solution. We compute $2^{2}=4$, $2^{3}=8$, $2^{4}=16\equiv 1\bmod 15$, so that

$$2^{27}=2^{4\cdot 6+3}=(2^{4})^{6}\cdot 2^{3}\equiv 1^{6}\cdot 8=8\bmod 15.$$

Solution. We compute $3^{2}=9\equiv 2\bmod 7$ and

$$3^{3}=3\cdot 3^{2}\equiv 3\cdot 2=6\equiv-1\bmod 7,$$

so that

$$3^{58}=3^{3\cdot 19+1}=(3^{3})^{19}\cdot 3\equiv(-1)^{19}\cdot 3=-3\equiv 4\bmod 7,$$

so the remainder is $4.$

Solution. We have $8\equiv 3\bmod 5$, so that $8^{2}\equiv 3^{2}=9\equiv-1\bmod 5$, and hence

$$8^{4n+2}=(8^{2})^{2n+1}\equiv(-1)^{2n+1}=-1\bmod 5.$$

Likewise, we see that $4^{2}=16\equiv 1\bmod 5$, so that

$$4^{2n}=(4^{2})^{n}\equiv 1^{n}=1\bmod 5,$$

and thus $8^{4n+2}+4^{2n}\equiv(-1)+1=0\bmod 5$, which proves the result.

What we have succeeded in defining in this section is called modular arithmetic; it has the great advantage over ordinary arithmetic of requiring only very small calculations as the set involved is finite, but as we have seen it sometimes enables us to answer questions which would otherwise seem impossibly hard.