3.2: Modulo Arithmetic

Last updated

May 14, 2022
Save as PDF
- 3.1: Modulo Operation
- 3.3: Divisibility rules revisited

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

$\newcommand{\vectorA}[1]{\vec{#1}} % arrow$

$\newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$

$\newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$

$\newcommand{\vectorC}[1]{\textbf{#1}}$

$\newcommand{\vectorD}[1]{\overrightarrow{#1}}$

$\newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}}$

$\newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}}$

$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$

$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$

$\newcommand{\avec}{\mathbf a}$

$\newcommand{\bvec}{\mathbf b}$

$\newcommand{\cvec}{\mathbf c}$

$\newcommand{\dvec}{\mathbf d}$

$\newcommand{\dtil}{\widetilde{\mathbf d}}$

$\newcommand{\evec}{\mathbf e}$

$\newcommand{\fvec}{\mathbf f}$

$\newcommand{\nvec}{\mathbf n}$

$\newcommand{\pvec}{\mathbf p}$

$\newcommand{\qvec}{\mathbf q}$

$\newcommand{\svec}{\mathbf s}$

$\newcommand{\tvec}{\mathbf t}$

$\newcommand{\uvec}{\mathbf u}$

$\newcommand{\vvec}{\mathbf v}$

$\newcommand{\wvec}{\mathbf w}$

$\newcommand{\xvec}{\mathbf x}$

$\newcommand{\yvec}{\mathbf y}$

$\newcommand{\zvec}{\mathbf z}$

$\newcommand{\rvec}{\mathbf r}$

$\newcommand{\mvec}{\mathbf m}$

$\newcommand{\zerovec}{\mathbf 0}$

$\newcommand{\onevec}{\mathbf 1}$

$\newcommand{\real}{\mathbb R}$

$\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}$

$\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}$

$\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}$

$\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}$

$\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$

$\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$

$\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$

$\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$

$\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}$

$\newcommand{\laspan}[1]{\text{Span}\{#1\}}$

$\newcommand{\bcal}{\cal B}$

$\newcommand{\ccal}{\cal C}$

$\newcommand{\scal}{\cal S}$

$\newcommand{\wcal}{\cal W}$

$\newcommand{\ecal}{\cal E}$

$\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}$

$\newcommand{\gray}[1]{\color{gray}{#1}}$

$\newcommand{\lgray}[1]{\color{lightgray}{#1}}$

$\newcommand{\rank}{\operatorname{rank}}$

$\newcommand{\row}{\text{Row}}$

$\newcommand{\col}{\text{Col}}$

$\renewcommand{\row}{\text{Row}}$

$\newcommand{\nul}{\text{Nul}}$

$\newcommand{\var}{\text{Var}}$

$\newcommand{\corr}{\text{corr}}$

$\newcommand{\len}[1]{\left|#1\right|}$

$\newcommand{\bbar}{\overline{\bvec}}$

$\newcommand{\bhat}{\widehat{\bvec}}$

$\newcommand{\bperp}{\bvec^\perp}$

$\newcommand{\xhat}{\widehat{\xvec}}$

$\newcommand{\vhat}{\widehat{\vvec}}$

$\newcommand{\uhat}{\widehat{\uvec}}$

$\newcommand{\what}{\widehat{\wvec}}$

$\newcommand{\Sighat}{\widehat{\Sigma}}$

$\newcommand{\lt}{<}$

$\newcommand{\gt}{>}$

$\newcommand{\amp}{&}$

$\definecolor{fillinmathshade}{gray}{0.9}$

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.

Search

Text Color

Text Size

Margin Size

Font Type

ISBN Check Digit

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]

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]

Theorem 5 :

Theorem 6:

Theorem 7:

Theorem 8:

Odd and Even integers:

ISBN Check Digit

Support Center

How can we help?

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]