3.2: Modulo Arithmetic

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

Addition

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

Answer

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

Answer

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

Answer

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

Answer

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.

Answer

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

Answer

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

Answer

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, .◻

 

Answer

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

For every positive integer , prove that is divisible by .

Answer

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.