## Section14.3Modular 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{.}$$

### Definition14.3.1.

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\text{.}$$ 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.3.3 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.

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.3.3.

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$$

In Checkpoint 14.3.4 and Checkpoint 14.3.5 compute some modular sums and products.

Fill in the operation table for the binary operation $$\oplus$$ on the set $$\mathbb{Z}_{3}$$ defined by $$a \oplus b = (a + b)\bmod 3$$ :

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

Complete the following:

(a) In $$\mathbb{Z}_{3}$$ with respect to $$\oplus$$

• select

• the identity element is 0

• the identity element is 1

• there is no identity element

.

(b) In $$\mathbb{Z}_{3}$$

• select

• each element has an inverse

• at least one element does not have an inverse

• there is no identity, so inverses are not defined

with respect to $$\oplus\text{.}$$

(c) The operation $$\oplus$$ is

• select

• associative

• not associative

.

(d) The operation $$\oplus$$ is

• select

• commutative

• not commutative

.

Conclude whether $$\left(\mathbb{Z}_{3},\oplus\right)$$ is a commutative group:

The set $$\mathbb{Z}_{3}$$ with the operation $$\oplus$$ is

• select

• a commutative group

• not a commutative group

.

$$0$$

$$1$$

$$2$$

$$1$$

$$2$$

$$0$$

$$2$$

$$0$$

$$1$$

$$\text{the identity element is 0}$$

$$\text{each element has an inverse}$$

$$\text{associative}$$

$$\text{commutative}$$

$$\text{a commutative group}$$

Let $$\mathbb{Z}_{61}={ 0,1,2,\dots, 61}\text{.}$$ Consider the binary operation $$\oplus:\mathbb{Z}_{61}\times \mathbb{Z}_{61}\to \mathbb{Z}_{61}$$ given by $$a \oplus b = \left(a + b\right) \bmod 61\text{.}$$

The identity with respect to $$\oplus$$ in $$\mathbb{Z}_{61}$$ is .

The inverse of $$18$$ with respect to $$\oplus$$ in $$\mathbb{Z}_{61}$$ is .

Hint.

An element $$e\in \mathbb{Z}_m$$ is the identity with respect to $$\oplus$$ if $$a \oplus e= a$$ and $$e \oplus a=a$$ for all $$a\in \mathbb{Z}_m\text{..}$$

An element $$b\in \mathbb{Z}_m$$ is the inverse of $$a\in \mathbb{Z}_m$$ with respect to $$\oplus$$ if $$a \oplus b=0$$ and $$b \oplus a=e\text{.}$$

Make sure that your answer is an element of $$\mathbb{Z}_m\text{.}$$

$$0$$

$$43$$

In Theorem 3.4.10 and Theorem 3.4.14 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.

Let m be a natural number. Let S={0,1,2,3,...,m-1}. Let $$\oplus\text{:}$$S$$\times$$S$$\to$$S be given by a$$\oplus$$b=(a+b) mod m.

We show that (S,$$\oplus$$) is a group.

(a) Because a$$\oplus$$0=

• a

• a-1

• 0

• 1

• 2

• m-a

• a-m

and 0$$\oplus$$a=
• a

• a-1

• 0

• 1

• 2

• m-a

• a-m

for all a in S, the element
• a

• a-1

• 0

• 1

• 2

• m-a

• a-m

is the
• analogue

• identity

• inverse

• opposite

with respect to the operation $$\oplus\text{.}$$

(b) For all a in S we have a$$\oplus$$

• a

• a-1

• 0

• 1

• 2

• m-a

• a-m

=0 and
• a

• a-1

• 0

• 1

• 2

• m-a

• a-m

$$\oplus$$a=0.

Thus each a in S has an

• analogue

• identity

• inverse

• opposite

with respect to the operation $$\oplus\text{.}$$

(c) The addition of integers is associative. That means

• (a+b)+c = a+(b+c)

• a+b = b+a

• a+0 = a and 0+a = a

• a+b = 0 and b+a = 0

for all integers a, b, and c.

Thus for for all a, b, and c in S we have

(a$$\oplus$$b)$$\oplus$$ c =

• ((a+b)+c) mod m

• (a+(b+c)) mod m

• (a+b) mod m

• (b+a) mod m

• (a(b+c)) mod m

• (ab+ac) mod m

=
• ((a+b)+c) mod m

• (a+(b+c)) mod m

• (a+b) mod m

• (b+a) mod m

• (a(b+c)) mod m

• (ab+ac) mod m

=a$$\oplus$$(b$$\oplus$$ c).

Hence the operation $$\oplus$$ is

• associative

• commutative

• disruptive

• distributive

• orderly

.

(d) The addition of integers is commutative. That means

• (a+b)+c = a+(b+c)

• a+b = b+a

• a+0 = a and 0+a = a

• a+b = 0 and b+a = 0

for all integers a and b.

Thus for all a and b in S we have

a$$\oplus$$b =

• ((a+b)+c) mod m

• (a+(b+c)) mod m

• (a+b) mod m

• (b+a) mod m

• (a(b+c)) mod m

• (ab+ac) mod m

=
• ((a+b)+c) mod m

• (a+(b+c)) mod m

• (a+b) mod m

• (b+a) mod m

• (a(b+c)) mod m

• (ab+ac) mod m

=b$$\oplus$$a.

Hence the operation $$\oplus$$ is

• associative

• commutative

• disruptive

• distributive

• orderly

.

We have shown that

(a) the set S contains an identity with respect to the operation $$\oplus\text{,}$$

(b) for each element in S the set S contains an inverse with respect to $$\oplus\text{,}$$

(c) the operation $$\oplus$$ is associative,

(d) the operation $$\oplus$$ is commutative.

Thus the set S with the operation $$\oplus$$ is a commutative group.

$$\text{a}$$

$$\text{a}$$

$$\text{0}$$

$$\text{identity}$$

$$\text{m-a}$$

$$\text{m-a}$$

$$\text{inverse}$$

$$\text{(a+b)+c = a+(b+c)}$$

$$\text{((a+b)+c) mod m}$$

$$\text{(a+(b+c)) mod m}$$

$$\text{associative}$$

$$\text{a+b = b+a}$$

$$\text{(a+b) mod m}$$
$$\text{(b+a) mod m}$$
$$\text{commutative}$$
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.