# 3.2: Modular Arithmetic

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$$

In this section, we will explore arithmetic operations in a modulo world.

Let $$n \in \mathbb{Z_+}$$.

### Theorem 5 :

Let $$a, b, c,d, \in \mathbb{Z}$$ such that $$a \equiv b (mod\,n)$$ and $$c \equiv d (mod\, n).$$ Then $$(a+c) \equiv (b+d)(mod\, n).$$

Proof:

Let $$a, b, c, d \in\mathbb{Z}$$, such that $$a \equiv b (mod\, n)$$ and $$c \equiv d (mod \,n).$$

We shall show that $$(a+c) \equiv (b+d) (mod\, n).$$

Since $$a \equiv b (mod\, n)$$ and $$c \equiv d (mod\, n), n \mid (a-b)$$ and $$n \mid (c-d)$$

Thus $$a= b+nk,$$ and $$c= d+nl,$$ for $$k$$ and $$l \in \mathbb{Z}$$.

Consider$$(a+c) -( b+d)= a-b+c-d=n(k+l), k+l \in \mathbb{Z}$$.

Hence $$(a+c)\equiv (b+d) (mod \,n).\Box$$

### Theorem 6: Let $$a, b, c,d, \in \mathbb{Z}$$ such that $$a \equiv b (mod \, n)$$ and $$c \equiv d (mod \,n).$$ Then $$(ac) \equiv (bd) (mod \,n).$$

Proof:

Let $$a, b, c, d \in \mathbb{Z}$$, such that $$a \equiv b (mod\, n)$$ and $$c \equiv d (mod \, n).$$

We shall show that $$(ac) \equiv (bd) (mod\, n).$$

Since $$a \equiv b (mod \,n)$$ and $$c \equiv d (mod\, n), n \mid (a-b)$$ and $$n \mid (c-d)$$

Thus $$a= b+nk,$$ and $$c= d+nl,$$ for $$k$$ and $$l \in \mathbb{Z}$$.

Consider $$(ac) -( bd)= ( b+nk) ( d+nl)-bd= bnl+dnk+n^2lk=n (bl+dk+nlk),$$ where $$(bl+dk+nlk) \in \mathbb{Z}$$.

Hence $$(ac) \equiv (bd) (mod \,n).\Box$$

### Theorem 7:

Let $$a, b \in$$ $$\mathbb{Z}$$ such that $$a \equiv b (mod \, n)$$. Then $$a^2 \equiv b^2 (mod \, n).$$

Proof:

Let $$a, b \in$$ $$\mathbb{Z}$$, and n $$\in$$ $$\mathbb{Z_+}$$, such that $$a \equiv b (mod \, n).$$

We shall show that $$a^2 \equiv b^2 (mod \, n).$$

Since $$a \equiv b (mod \, n), n\mid (a-b).$$

Thus $$(a-b)= nx,$$ where $$x \in$$ $$\mathbb{Z}$$.

Consider $$(a^2 - b^2) = (a+b)(a-b)=(a+b)(nx), = n(ax+bx), ax+bx \in \mathbb{Z}$$.

Hence $$n \mid a^2 - b^2,$$ therefore $$a^2 \equiv b^2 (mod \, n).$$ $$\Box$$

### Theorem 8:

Let $$a, b \in$$ $$\mathbb{Z}$$ such that $$a \equiv b (mod \, n)$$. Then $$a^m \equiv b^m (mod \, n)$$, $$\forall \in$$ $$\mathbb{Z}$$.

Proof:

Exercise.

By using the above result we can solve many problems. Some of them are discussed below:

Example $$\PageIndex{1}$$: $$mod\, 3$$ Arithmetic

Let $$n = 3$$.

 +               

Multiplication

 x               

Example $$\PageIndex{2}$$: $$mod\, 4$$ Arithmetic

Let $$n=4$$.

 x                        

Example $$\PageIndex{3}$$:

Find the remainder when $$(101)(103)(107)(109)$$ is divided by $$11.$$

$$101 \equiv 2 (mod \, 11)$$

$$103 \equiv 4 (mod \, 11)$$

$$107 \equiv 8 (mod \, 11)$$

$$109 \equiv 10 (mod \,11)$$.

Therefore,

$$(101)(103)(107)(109) \equiv (2)(4)(8)(10) (mod \,11) \equiv 2 (mod \,11)$$.

Example $$\PageIndex{4}$$:

Find the remainder when$$7^{1453}$$ is divided by $$8.$$

$$7^0 \equiv 1 (mod \, 8)$$

$$7^1 \equiv 7 (mod \, 8)$$

$$7^2 \equiv 1 (mod \, 8)$$

$$7^3 \equiv 7 (mod \, 8)$$,

As there is a consistent pattern emerging and we know that $$1453$$ is odd, then $$7^{1453} \equiv 7 (mod \, 8)$$. Thus the remainder is $$7.$$

Example $$\PageIndex{5}$$:

Find the remainder when $$7^{2020}$$ is divided by $$18.$$

$$7^0 \equiv 1 (mod \, 18)$$

$$7^1 \equiv 7 (mod \, 18)$$

$$7^2 \equiv 13 (mod \, 18)$$

$$7^3 \equiv 1 (mod \, 18)$$,

As there is a consistent pattern emerging and we know that $$2020=(673)3+1$$, $$7^{2020}= 7^{(673)3+1}=\left( 7^3\right)^{673}7^1 \equiv 7 (mod \, 18).$$ Thus the remainder is $$7.$$

Example $$\PageIndex{6}$$:

Find the remainder when $$26^{1453}$$ is divided by $$3.$$

This page titled 3.2: Modular Arithmetic is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Pamini Thangarajah.