Skip to main content
Logo image

Section 14.3 Modular Addition and Multiplication

In Section 3.4 we have encountered the addition of hours, weekdays, and months as an example for modular arithmetic. We now introduce binary operations on the sets \(\Z_n=\{0,1,2,\dots,n-1\}\) where \(n\in\N\) based on the addition and multiplication of integers. For \(a\) and \(b\) in \(\Z_n\) we consider \((a+b)\fmod n\) and \((a\cdot b)\fmod n\text{.}\) Because the remainder of division by \(n\) is always an element of \(\Z_n=\{0,1,2,\dots,n-1\}\) these yield binary operations on \(\Z_n\text{.}\)

Definition 14.13.

Let \(n\in\N\text{.}\) We define two binary operations on the set
\begin{equation*} \Z_n=\{0,1,2,\dots,n-1\}\text{.} \end{equation*}
  1. We call \(\oplus:\Z_n\times\Z_n\to\Z_n\text{,}\) \(a\oplus b:=(a+b)\fmod n\) addition modulo \(n\).
  2. We call \(\otimes:\Z _n\times\Z_n\to\Z_n\text{,}\) \(a\otimes b:=(a\cdot b)\fmod n\) multiplication modulo \(n\).
We have already encountered operation tables for modular addition and multiplication Chapter 13. In Table 14.15 we present the operations tables for addition and multiplication modulo \(7\) side by side. Once these tables are created modular addition or multiplication can be done by table lookup.

Example 14.14. Arithmetic modulo \(7\).

We present examples for addition and multiplication modulo 7. Let \(a\oplus b:=(a+b)\fmod 7\) and \(a\otimes b:=(a\cdot b)\fmod 7\text{.}\) Tables for the binary operations \(\oplus\) and \(\otimes\) are given in Table 14.15.
  1. \(5\otimes 4=(5\cdot 4)\fmod 7\) \(=20\fmod 7=6\)
  2. \(3\oplus 4=(3+4)\fmod 7\) \(==7\fmod 7=0\)
  3. \(2\otimes(3\oplus 6)=2\otimes((3+6)\fmod 7)\) \(=(2\otimes (9\fmod 7))\) \(=2\otimes 2=(2\cdot 2)\fmod 7\) \(=4\fmod 7=4 \)
Table 14.15. Addition and multiplication tables for arithmetic modulo 7, that is, for the operations given by \(a\oplus b=(a+b)\fmod 7\) and \(a\otimes b=(a\cdot b)\fmod 7\text{.}\)
In Checkpoint 14.16 and Checkpoint 14.17 compute some modular sums and products.

Checkpoint 14.16. Modular addition.

Let \(\oplus:\mathbb{Z}_{97}\times\mathbb{Z}_{97}\to\mathbb{Z}_{97}\) be defined by \(a\oplus b= (a +b) \bmod 97\text{.}\)
Compte
\(56\oplus 68 =\)
\(68\oplus 56 =\)
\((81\oplus 90)\oplus 50 =\)
\(81\oplus (90\oplus 50) =\)

Checkpoint 14.17. Modular multiplication.

Let \(\otimes:\mathbb{Z}_{37}^\otimes\times\mathbb{Z}_{37}^\otimes\to\mathbb{Z}_{37}^\otimes\) be defined by \(a\otimes b= (a \cdot b) \bmod 37\text{.}\)
Compute
\(11\otimes 31 =\)
\(31\otimes 11 =\)
\(19\otimes 20 =\)
\(20\otimes 19 =\)
\((16\otimes 7)\otimes 9 =\)
\(16\otimes (7\otimes 9) =\)
\((11\otimes 21)\otimes 18 =\)
\(11\otimes (21\otimes 18) =\)
In Theorem 3.46 and Theorem 3.50 we had seen that addition and multiplication and \(\fmod\) work nicely together. These properties help make modular arithmetic easier as they help to keep the size of numbers small.

Checkpoint 14.18. Modular arithmetic.

Let \(a:=9638\text{,}\) \(b:=5920\text{,}\) \(c:=30\text{,}\) and \(d:=8423\text{.}\)
Compute:
\(a \bmod 10 =\)
\(b \bmod 10 =\)
\(c \bmod 10 =\)
\(d \bmod 10 =\)
Now use these to compute the following:
\((a + b)\bmod 10 =\)
\((c + d)\bmod 10 =\)
\(( b\cdot c)\bmod 10 =\)
\(( d\cdot a)\bmod 10 =\)
In the following two section we apply modular addition and multiplication in the definition of certain groups. We show that for any \(n\in\N\text{,}\) the set \(\Z_n\) with addition modulo \(n\) is a group and that for any prime number \(p\) the set \(\Z_p^\otimes\) with multiplication modulo \(p\) is a group.