# 3.2: Modular Arithmetic

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}[1]{\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]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\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]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\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$$.

 + [0] [1] [2] [0] [0] [1] [2] [1] [1] [2] [0] [2] [2] [0] [1]

Multiplication

 x [0] [1] [2] [0] [0] [0] [0] [1] [0] [1] [2] [2] [0] [2] [1]

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

Let $$n=4$$.

 x [0] [1] [2] [3] [0] [0] [0] [0] [0] [1] [0] [1] [2] [3] [2] [0] [2] [0] [2] [3] [0] [3] [2] [1]

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

## Odd and Even integers:

An integer $$n$$ is even iff $$n\equiv 0(mod \, 2).$$

An integer $$n$$ is odd iff $$n\equiv 1(mod \, 2).$$

Two integers a and b are said to have some parity if they are both even or both odd otherwise a and b are said to have different parity.

Example $$\PageIndex{6}$$:

Show that the sum of an odd integer and an even integer is odd.

Proof: Let $$a$$ be an odd integer and let $$b$$ be an even integer. We shall show that $$a+b$$ is odd by using the language of congruency.

Since $$a$$ is odd, $$a \equiv 1 (mod \, 2).$$

Since $$b$$ is even, $$b \equiv 0 (mod \, 2).$$

Then $$(a+b) \equiv (1+0)(mod \, 2),$$

$$(a+b) \equiv 1 (mod \, 2).$$

Hence $$a+b$$ is odd.$$\Box$$

Example $$\PageIndex{7}$$:

Show that the product of an odd integer and an even integer is even.

Proof: Let $$a$$ be an odd integer and let $$b$$ be an even integer. We shall show that $$ab$$ is even by using the language of congruency.

Since $$a$$ is odd, $$a \equiv 1 (mod \, 2).$$

Since $$b$$ is even, $$b \equiv 0 (mod \, 2).$$

Then $$(ab) \equiv (1)(0)(mod \, 2),$$

$$(ab) \equiv 0 (mod \, 2).$$

Hence $$ab$$ is even.$$\Box$$

Example $$\PageIndex{8}$$:

Show that $$n^2+1$$ is not divisible by $$3$$ for any integer $$n.$$

Proof: Let $$n \in \mathbb{Z}$$. We shall show that $$(n^2+1)$$ is not divisible by $$3$$ using the language of congruency.

We shall show that $$(n^2+1)(mod \,3) \not \equiv 0$$ by examining the possible cases.

Case 1: $$n \equiv 0 (mod \, 3).$$

$$n^2 \equiv 0^2 (mod \,3).$$

$$(n^2+1) \equiv 1 (mod \,3).$$

Hence $$n^2+1$$ is not divisible by $$3.$$

Case 2: $$n \equiv 1 (mod \, 3).$$

$$n^2 \equiv 1^2 (mod \,3).$$

$$(n^2+1) \equiv 1 (mod \,3).$$

Hence $$n^2+1$$ is not divisible by $$3.$$

Case 3: $$n \equiv 2 (mod \, 3).$$

$$n^2 \equiv 2^2 (mod \,3) \equiv 1 (mod \,3).$$

$$(n^2+1) \equiv 2 (mod \,3).$$

Hence $$n^2+1$$ is not divisible by $$3.$$

Since none of the possible cases is congruent to $$0 (mod \, 3), n^2+1$$ is not divisible by $$3.$$ $$\Box$$

Example $$\PageIndex{9}$$:

Show that $$5 \mid a^5+4a$$ for any integer $$a.$$

Notice that $$4 \equiv -1 (mod \, 5).$$ Therefore, $$5 \mid a^5+4a$$ iff $$5 \mid a^5-a$$ for all integer $$a$$.

Let .

We shall show that .

Then and .

We will proceed by examining the 5 possible cases of $$.$$ Specifically, .

Case : If then

.

Thus .

Case : If then

.

Thus .

Case : If then

.

Thus .

Case : If then

.

Thus .

Case : If then

.

Thus .

Having examined all possible cases, .◻

Let where and .

Then .

Thus . Rearranging, we obtain .

Consider

.

Let .

Since , then .

Thus .

Clearly, . We shall examine the possible cases of .

Case b=0: If then . Thus .

Case b=1: If then and where q .

Thus .

Case b=2: If then and .

Thus .

Case b=3: If then and .

Thus .

Case b=4: If then and .

Thus .

Having examined all possible cases, .◻

Example $$\PageIndex{10}$$

Proof:

Let be the statement .

says that .

says that . Since and , is true.

Assume is true for some .

We will show that is true.

Specifically, we will show that .

Consider that

.

Since , .

Let .

Thus .

Having shown the inductive step, for every positive integer , is divisible by .

## ISBN Check Digit

ISBN is the abbreviation for the International Standard Book Number. ISBN numbers are 10 digits in length. In an ISBN of the form X-XX-XXXXXX-X:

• The first block of digits on the left represents the language of the book (0 is used to represent English).
• The second block of digits represents the publisher.
• The third block of digits represents is the number assigned to the book by the publishing company.
• The fourth block consists of the check digit.

Consider the ISBN 0-13-190190-?

To determine the check digit for this Book Number, follow the below steps.

Step 1: Multiply all nine assigned digits by weighted values. The weighted values are 1 for the first digit from the left, 2 for the second digit, three for the third digit, etc.

$$1*0 + 2*1 + 3*3 + 4*1 + 5*9 + 6*0 + 7*1 + 8*9 + 9*0 = 139$$.

Step 2: ISBN uses $$(mod \, 11)$$ to determine the check digit. So $$139 = 11(11) + 7$$ so $$139 \equiv 7 (mod \,11)$$. Hence the check digit is $$7$$. Note that $$X$$ is used for $$10$$.

If someone orders a book by the ISBN number then the check digit is a way of ensuring that the number was reported and recorded correctly so that the correct book is obtained.

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.