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{.}\)
Definition14.13.
Let \(n\in\N\text{.}\) We define two binary operations on the set
We call \(\oplus:\Z_n\times\Z_n\to\Z_n\text{,}\)\(a\oplus b:=(a+b)\fmod n\)addition modulo \(n\).
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.
Example14.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.
Table14.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{.}\)
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) =\)
Checkpoint14.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.
Checkpoint14.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.
