1.21: Addition and Multiplication in Zm

In this chapter we show how to define addition and multiplication of residue classes modulo $m$. With respect to these binary operations $\mathbb{Z}_m$ is a ring as defined in Appendix A.

Definition $\PageIndex{1}$

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

Example $\PageIndex{1}$

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{aligned} \left[2\right]+[3]&=[0] \\ [2][3]&=[1].\end{aligned}$$

Since a residue class can have many representatives, it is important to check that the rules given in Definition $\PageIndex{1}$ 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{1}$

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

Proof

(This follows immediately from Theorem 15.3 and Theorem 19.2.)

Exercise $\PageIndex{1}$

Prove Theorem $\PageIndex{1}$.

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

Example $\PageIndex{2}$

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 all residue classes in the least nonnegative residue system, as we do in constructing the following addition and multiplication tables for $\mathbb{Z}_4$.

Table $\PageIndex{1}$

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

Table $\PageIndex{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 Exercise 15.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,

$$[a]+[b]=[(a+b)\bmod m]\nonumber$$

$$[a][b]=[(ab)\bmod m]\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]$ in the same set. This leads to an alternative way to define $\mathbb{Z}_m$ and addition and multiplication in $\mathbb{Z}_m$. For clarity we will use different notation.

Definition $\PageIndex{2}$

For $m>0$ define $$J_m=\{0,1,2,\dotsc,m-1\}\nonumber$$ and for $a,b\in J_m$ define $$\begin{aligned} a\oplus b &=(a+b)\bmod m \\ a\odot b &=(ab)\bmod m.\end{aligned}$$

Remark $\PageIndex{1}$

$J_m$ with $\oplus$ and $\odot$ as defined is isomorphic to $\mathbb{Z}_m$ with addition and multiplication given by Definition $\PageIndex{1}$. [Students taking 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 $J_4$ are:

Table $\PageIndex{3}$

$\oplus$	$0$	$1$	$2$	$3$
$0$	$0$	$1$	$2$	$3$
$1$	$1$	$2$	$3$	$0$
$2$	$2$	$3$	$0$	$1$
$3$	$3$	$0$	$1$	$2$

Table $\PageIndex{4}$

$\odot$	$0$	$1$	$2$	$3$
$0$	$0$	$0$	$0$	$0$
$1$	$0$	$1$	$2$	$3$
$2$	$0$	$2$	$0$	$2$
$3$	$0$	$3$	$2$	$1$

Exercise $\PageIndex{2}$

Prove that for every modulus $m>0$ we have for all $a,b\in J_m$ $$[a]+[b]=[a\oplus b],\nonumber$$ and $$[a][b]=[a\odot b].\nonumber$$

Exercise $\PageIndex{3}$

Construct addition and multiplication tables for $J_5$.

Exercise $\PageIndex{4}$

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

Example $\PageIndex{3}$

Let’s solve the congruence $$\label{eq:1} 272x\equiv 901\pmod 9.$$ Using residue classes modulo $9$ we see that (1) is equivalent to $$\label{eq:2} [272x]=[901]$$ which is equivalent to $$\label{eq:3} [272][x]=[901]$$ which is equivalent to $$\label{eq:4} [2][x]=[1].$$ Now we know $[x]\in\{[0],[1],\dotsc,[8]\}$ so by trial and error we see that $x=5$ is a solution.