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.