Modular Arithmetic and Algorithms

Objectives

Students will:

(1.) Write several algorithms and theorems involving integers.
(2.) Solve expressions involving integers modulo an integer.
(3.) Solve equations involving modulo.
(4.) Draw modulo tables involving addition.
(5.) Draw modulo tables involving multiplication.
(6.) Calculate the least common multiple of two or more integers using the Listing Method.
(7.) Calculate the least common multiple of two or more integers using the Nigerian Method.
(8.) Calculate the least common multiple of two or more integers using the Prime Factorization Method.
(9.) Calculate the greatest common factor of two or more integers using the Listing Method.
(10.) Calculate the greatest common factor of two or more integers using the Nigerian Method.
(11.) Calculate the greatest common factor of two or more integers using the Prime Factorization Method.
(12.) Represent integers using different number systems.
(13.) Convert integers from one number system to another number system.
(14.) Perform arithmetic operations on integers represented in different number systems.
(15.) Discuss modular arithmetic.
(16.) Solve expressions involving modular arithmetic.
(17.) Solve equations involving modular arithmetic.
(18.) Check the solutions of equations involving modular arithmetic.
(19.) Draw modulo tables involving addition and multiplication.
(20.) Determine the greatest common divisor of two integers using the Euclidean Algorithm.
(21.) Determine the modular inverse of an integer modulo another integer.
(22.) Determine the greatest common divisor of two integers, the Bezout's coefficients, and the modular inverse of an integer modulo another integer using the Extended Euclidean Algorithm.
(23.) Solve a linear congruence problem.
(24.) Check the solution of a linear congruence problem.
(25.) Solve a system of linear congruencies using the Chinese Remainder Theorem.
(26.) Solve a system of linear congruencies using the Back Substitution Method.
(27.) Check the solution of a system of linear congruencies.
(28.) Solve a modular exponentiation problem using the Modular Exponentiation Algorithm (Method of Repeated Squaring).
(29.) Solve a modular exponentiation problem using the Fast Modular Multiplication method.
(30.) Solve a modular exponentiation problem using Fermat's Little Theorem.
(31.) Solve a modular exponentiation problem using Fermat's Little Theorem and the Chinese Remainder Theorem.
(32.) Discuss several modular arithmetic applications.
(33.) Solve applied problems involving modular arithmetic and algorithms.

Vocabulary Words

bit, digital, base, binary, binary digit, two, decimal, ten, octal, eight, hexadecimal, sixteen, integer, face value, place value, sum, difference, product, quotient, augend, addend, minuend, subtrahend, multiplier, multiplicand, factor, dividend, divisor, positive, negative, nonpositive, nonnegative, modulo, modular arithmetic, gcd, greatest common divisor, lcm, least common multiple, hcf, highest common factor, gcm, greatest common measure, modular algorithm, gcd, greatest common divisor, Euclidean algorithm, Fermat's little theorem, exponent, base, extended Euclidean algorithm, modular inverse, Chinese remainder theorem, linear congruence, congrunence, equivalence, equivalence classes, binary, decimal, octal, hexadecimal, base two, base ten, base six, base eight, base sixteen, modular exponentiation, Bezout's coefficients, ternary, quaternary, exponents, quinary, senary, septenary, nonary, decimal, undecimal, duodecimal, tridecimal, tetradecimal, pentadecimal, greatest common measure, highest common factor, gcm, hcf, least common multiple, lcm, least common denominator, lcd, coprimes, relatively prime, mutually prime, division, algorithm, division algorithm, dividend, divisor, quotient, remainder, augend, addend, minuend, subtrahend, sum, difference, product, multiplier, multiplicand, positive, nonnegative, negative, nonpositive, numbers, bit, digit, binary digit, integers, whole numbers, fast multiplication, algorithm, repeated squaring, division algorithm, linear congruences, congruence class

Symbols and Meanings

Definitions

Number Systems

Recall:
What are the number systems?
Which system did you use in the elementary school?
Which system is used for machine learning?
Which systems are used for computer architecture?

Number System is a system of expressing numbers.
It is also known as a Numeral System.

Integer Representations

Normally, we use the decimal number system (base $10$) to represent integers.
This implies that we use ten symbols to represent integers. These are: $0, 1, 2, 3, 4, 5, 6, 7, 8, \:and\: 9$
A digital computer uses the binary number system (base $2$).
Data is encoded in a digital computer in bits.
This implies that a computer uses $0 \:and\: 1$ to represent integers.

Ask students if they now realize the need to study both systems.
But, why study octal and hexadecimal systems too?

Octal system (base $8$) represents integers using eight symbols.
Hexadecimal system (base $16$) represents integers using sixteen symbols.
Is your computer a $32-bit$ or $64-bit$ computer?
Imagine writing a 32-bit (a 32-binary digit) integer! Is there a way to shorten it?
Yes! That is the reason we represent them in octal and hexadecimal systems.
Ask student to list the digits used in the octal system.
Ask students to list the digits used in the hexadecimal system. Some may get it incorrect. But, that's fine. We shall return to it.

$2^3 = 8$
Each digit in the octal system is equivalent to three binary digits. (three digits in a binary system).
$2^4 = 16$
Each digit in the hexadecimal system is equivalent to four binary digits.

Ask students to display any scientific or graphing calculator they may have.
Look for: BIN, DEC, OCT, HEX
Ask them the meaning of those abbreviations.

Recall: Face values and Place values. You probably did this in elementary grade ☺
For the integer: $523$
The face value of $3$ is $3$, and the place value of $3$ is also $3$
The face value of $2$ is $2$, but the place value of $2$ is $20$. This means that the $2$ actually represents $20$
The face value of $5$ is $5$, but the place value of $5$ is $500$. This means that the $5$ represents $500$.
Hence, you read the number as: $five \: hundred\: and\: twenty\: three$

Bring it to Number Theory
The number, $523$ is an integer represented in the decimal system (base $10$)
We begin from the right.
$3$ actually means $3 * 10^0$ = $3 * 1$ = $3$
$2$ actually means $2 * 10^1$ = $2 * 10$ = $20$
$5$ actually means $5 * 10^2$ = $5 * 100$ = $500$.

Say we have the number, $1011$ in the binary system (base $2$)
We begin from the right.
The place value of that last $1$ is $1 * 2^0$ = $1 * 1$ = $1$
The place value of the $1$ before it is $1 * 2^1$ = $1 * 2$ = $2$
The place value of the $0$ is $0 * 2^2$ = $0 * 4$ = $0$
The place value of the first $1$ is $1 * 2^3$ = $1 * 8$ = $8$

Let us add: $1 + 2 + 0 + 8 = 11$
Do you realize that $11$ (meaning $11$ in base ten) is the same as $1011$ (in base two)?
We have just converted from base two (binary) to base ten (decimal)!
That is the way we convert from any base two to base ten
That is also the way we convert from any base to base ten!

So, to convert from a number in any base to its equivalent number in base ten:
(1.) Multiply each face value of that number with it's corresponding place value.
(2.) Add the products. (Sum of products). That sum gives the decimal expansion.

What if we wanted to convert a number in any base to another number in any base?
We can use at least four methods.

First Method: Intermediate Base Ten Method
This method is used to convert a number in any base to another number in any base.
Say you want to convert a number in base $c$ to another number in base $d$
First: You convert the number in the given base, base $c$ to a number in base ten.
Then, you convert that number in base ten to another number in base $d$
In this method, we use base ten as the "middle guy" or the intermediate guy.
This method is the most efficient method.

Second Method: $BIN \rightarrow DEC \rightarrow HEX \rightarrow OCT \rightarrow QUA\:$ Conversion Table
This method is used for conversion of numbers in binary, decimal, hexadecimal, octal, and quaternary bases.
We want to convert numbers between any of those bases - BIN, DEC, HEX, OCT, QUA.
We have to form a table that displays numbers in base two, ten, four, eight, and sixteen.
Let us discuss an easy way to draw this table.
The main "guy" for this table is base two. Why?
$2^2 = 4$
$2^3 = 8$
$2^4 = 16$
Do you see why base two is the "main" guy?
This means that a digit in base four represents two digits in base two. $4 = 2^2$
A digit in base eight represents three digits in base two. $8 = 2^3$
A digit in base sixteen represents four digits in base two. $16 = 2^4$
A digit in base sixteen represents how many digits in base four? Why?

Watch me do this! Practice it and you will see you will learn it!
Only $0 \:and\: 1$ are in base two
Since $2^4 = 16$, we shall write numbers in base two in four digits so we can just cover numbers in base sixteen.
Let us write $0 \:and\: 1$ in four digits in order. We have to get sixteen values.
$0000$
$0001$
$0010$
$0011$
$0100$
$0101$
$0110$
$0111$
$1000$
$1001$
$1010$
$1011$
$1100$
$1101$
$1110$
$1111$

Ask students if they notice any pattern in the last digits of each value. What did they notice?
If they feel they may skip any step, or if they feel they do not get it; then they should do each conversion the long way.
If they want to be sure they got each right, they can do each conversion the long way.

Let us summarize all the information.

$BIN \rightarrow DEC \rightarrow HEX \rightarrow OCT \rightarrow QUA\:$ Conversion Table

Third Method: $BIN \rightarrow QUA, \: OCT, \: HEX \:$ Method
This method is used to convert a number in base two to another number in any of bases four, eight, and/or sixteen.
This is because:
$2^2 = 4$
Each digit in base four is equivalent to two digits in base two.
$2^3 = 8$
Each digit in base eight is equivalent to three digits in base two.
$2^4 = 16$
Each digit in base sixteen is equivalent to four digits in base two.
In this method, write out the number in base two (the face values) first.
Break up the digits from the last value (from right to left) two digits at a time if you want to do $BIN \rightarrow QUA$
Break up the digits from the last value (from right to left) three digits at a time if you want to do $BIN \rightarrow OCT$
Break up the digits from the last value (from right to left) four digits at a time if you want to do $BIN \rightarrow HEX$
Fill any first set of incomplete digits with zeros.
Then, write the corresponding place values under the face value of each digit.
Draw a line under the place values (as you would do with arithmetic operations)
For each face value of $0$, write a $0$ under the line (beneath the place value).
For each face value that is non-zero, write the corresponding place value beneath the place value.
Add the digits of your result - two at a time in the case of $BIN \rightarrow QUA$
Add the digits of your result - three at a time in the case of $BIN \rightarrow OCT$
Add the digits of your result - four at a time in the case of $BIN \rightarrow HEX$

Fourth Method: $QUA \rightarrow \: HEX \:$ Method
This method is used to convert a number in base four to another number in base sixteen.
This is because:
$4^2 = 16$
Each digit in base sixteen is equivalent to two digits in base four.
In this method, write out the number in base four (the face values) first.
Break up the digits from the last value (from right to left) two digits at a time
Fill any first set of incomplete digits with zeros.
Then, write the corresponding place values under the face value of each digit.
Draw a line under the place values (as you would do with arithmetic operations)
For each face value of $0$, write a $0$ under the line (beneath the place value).
For each face value that is non-zero, write the corresponding place value beneath the place value.
Add the digits of your result - two at a time.

Arithmetic Operations

We can add, subtract, multiply, and divide non-negative integers in any base.
We can also express the result (sum, difference, product, and quotient) in any base.
The arithmetic operations on numbers in any base is performed just as they done in base ten.
However, it is important to note the numbers that can be allowed in any given base.
Let us do some examples.

(1.) $10_2 + 11_2$
$Augend = 10$
$Addend = 11$
Perform the usual addition...add each digit of the augend to the corresponding digit of the addend
Begin from the last digits
Carry over any excess and add the precedent digit of the augend
Note that only $0's$ and $1's$ are allowed in base two.
Set up the addition process $$ \begin{align} 1\ \ 0\ \ \\ + \ \ 1\ \ 1\ \ \\ \hline \end{align} $$ Last digits of augend and addend
$0 + 1 = 1$
Bring down $1$

$$ \begin{align} 1\ \ 0\ \ \\ + \ \ 1\ \ 1\ \ \\ \hline \ \ \ \ 1\ \ \end{align} $$ First digits of augend and addend
$1 + 1 = 2$
But $2_{10} = 10_2$
So, $1 + 1 = 10$ $$ \begin{align} 1\ \ 0\ \ \\ + \ \ 1\ \ 1\ \ \\ \hline 1\ \ 0\ \ 1\ \ \\ \hline \end{align} $$ $\therefore 10_2 + 11_2$ = $101_2$

(2.) $10_2 * 11_2$
$Multiplier = 10$
$Multiplicand = 11$
Perform the usual multiplication...multiply each digit of the multiplier by each digit of the multiplicand
Begin from the last digits
Note that only $0's$ and $1's$ are allowed in base two.
Set up the multiplication process $$ \begin{align} 1\ \ 0\ \ \\ * \ \ 1\ \ 1\ \ \\ \hline \end{align} $$ $1 * 0 = 0$
$1 * 1 = 1$

$1 * 0 = 0$
$1 * 1 = 1$ $$ \begin{align} 1\ \ 0\ \ \\ * \ \ 1\ \ 1\ \ \\ \hline 1\ \ 0\ \ \\ 1\ \ 0~~~~\ \ \\ \hline \end{align} $$ Then add. Remember that multiplication is repeated addition.
$$ \begin{align} 1\ \ 0\ \ \\ * \ \ 1\ \ 1\ \ \\ \hline 1\ \ 0\ \ \\ +\ \ 1\ \ 0~~~~\ \ \\ \hline 1\ \ 1\ \ 0\ \ \\ \hline \end{align} $$ $10_2 * 11_2$ = $110_2$

(3.) $11_2 + 11_2$
The red color is the carry over (carry) $$ \begin{align} \color{red}{1~~~~~~} \\ 1\ \ 1\ \ \\ + \ \ 1\ \ 1\ \ \\ \hline 1\ \ 1\ \ 0\ \ \\ \hline \end{align} $$ $3_{10} = 11_2$
$11_2 + 11_2$ = $110_2$

(4.) $11_2 * 11_2$
The red color is the carry over (carry) $$ \begin{align} 1\ \ 1\ \ \\ * \ \ 1\ \ 1\ \ \\ \hline \color{red}{1~~~~~~} \\ 1\ \ 1\ \ \\ \color{red}{1~~~~~~~~~~} \\ 1\ \ 1~~~~\ \ \\ \hline 1\ \ 0\ \ 1\ \ 1\ \ \\ \hline \end{align} $$ $3_{10} = 11_2$
$2_{10} = 10_2$
$11_2 * 11_2$ = $1011_2$

(5.) $111_2 + 111_2$
The red color is the carry over (carry) $$ \begin{align} \color{red}{1~~1~~~~~~} \\ 1\ \ 1\ \ 1\ \ \\ + \ \ 1\ \ 1\ \ 1\ \ \\ \hline 1\ \ 1\ \ 1\ \ 0\ \ \\ \hline \end{align} $$ $2_{10} = 10_2$
$3_{10} = 11_2$
$111_2 + 111_2$ = $1110_2$

(6.) $111_2 * 111_2$
The red color is the carry over (carry) $$ \begin{align} 1\ \ 1\ \ 1\ \ \\ * \ \ 1\ \ 1\ \ 1\ \ \\ \hline \color{red}{1~~~~~~~~~~} \\ \color{red}{11~~} 1\ \ 1\ \ 1\ \ \\ \color{red}{11~~} 1\ \ 1\ \ 1~~~~\ \ \\ 1\ \ 1\ \ 1~~~~~~~~\ \ \\ \hline 1\ \ 1\ \ 0\ \ 0\ \ 0\ \ 1\ \ \\ \hline \end{align} $$ $2_{10} = 10_2$...carry $1$
$3_{10} = 11_2$
$4_{10} = 100_2$...carry $2$. I wrote $11$ (one...one) because you cannot have $2$ in base two.
$111_2 * 111_2$ = $110001_2$

Modulo, GCD, and LCM

Modular Arithmetic

Numbers in a given modulo "wrap around".
They reach a certain value, and then continue from the beginning up to that value. Then, begin again.
A good example is the time as seen in the clock or watch.
In a $12-hour$ format, the time starts at 12 midnight $00:00\: am$; then continues till $11:59\: am$; and gets back to $00:00\: pm$
It does not include the number, $12$. Why?
It only includes the numbers $0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, \:and\: 11$.

Ask students if they noticed anything based on the lesson you just covered - Number Bases
What number base would they call that?
What about the time in a $24-hour$ format? How does it work? What number does it begin? What number does it end?
$3:00\: pm$ in a $12-hour$ format is equivalent to what time in a $24-hour$ format?
What are some organizations that use the $12-hour$ format? $24-hour$ format?

Say: it is $7:00\: am$
Your friend asks you what time it will be $9$ hours from now.
Ask students to respond.
$9 + 7 = 16$
It should be $16:00$ $(24-hour)$ format, or $4:00\: pm$ $12-hour)$ format
This means that $16 \mod 12 = 4$ (12-hour) format) OR
This means that $16 \mod 24 = 16$ (24-hour format)

$ 16\mod 12 \\[3ex] 16 = dividend \\[3ex] 12 = divisor \\[3ex] 16 \div 12 = 1\: R\: 4 \\[3ex] \dfrac{16}{12} = 1\dfrac{4}{12} = 1 + \dfrac{4}{12} \\[5ex] Remainder = 4 \\[3ex] \therefore\: 16 \mod 12 = 4 \\[7ex] 16 \mod 24 \\[3ex] 16 \div 24 = 0\: R\: 16 \\[3ex] \dfrac{16}{24} = 0\dfrac{16}{24} = 0 + \dfrac{16}{24} \\[5ex] Remainder = 16 \\[3ex] \therefore\: 16 \mod 24 = 16 \\[7ex] $ So, a dividend modulo a divisor is the remainder.
We are just interested in the remainder.

Can we do this another way (another method)?

$ 16 \mod 12 \\[3ex] 12 = 0 \\[3ex] 13 = 1 \\[3ex] 14 = 2 \\[3ex] 15 = 3 \\[3ex] 16 = 4 \\[3ex] \therefore 16 \mod 12 = 4 \\[7ex] 12 \mod 9 \\[3ex] 9 = 0 \\[3ex] 10 = 1 \\[3ex] 11 = 2 \\[3ex] 12 = 3 \\[3ex] \therefore 12 \mod 9 = 3 \\[7ex] $ Ask students if they like this method.
So far, we have been dealing with positive dividends.
What about negative dividends? What should we do in such cases?

Do we have negative divisors? Why or Why not?
Explain why you can have negative dividends, but not negative divisors.

$ \dfrac{7}{2}\:\:is\:\:also\:\: 2 | 7 \\[5ex] 2 | 7 \:means\: 2 \:divides\: 7 \:\:\:OR\:\:\: 7 \:divided\: by\: 2 \\[3ex] 2 | 7 = 3\: remainder\: 1 \\[3ex] \dfrac{7}{2} = 3\dfrac{1}{2} \\[5ex] 7 = 2 * 3 + 1 \\[3ex] 7 \:is\: the\: dividend \\[3ex] 2 \:is\: the\: divisor \\[3ex] 3 \:is\: the\: quotient \\[3ex] 1 \:is\: the\: remainder \\[5ex] \dfrac{a}{b}\:\:is\:\:also\:\: b | a \\[5ex] b | a \:means\: b \:divides\: a \:\:\:OR\:\:\: a \:divided\: by\: b \\[3ex] b | a = q\: remainder\: r \\[3ex] \dfrac{a}{b} = q\dfrac{r}{b} \\[5ex] a = b * q + r \\[3ex] a \:is\: the\: dividend \\[3ex] b \:is\: the\: divisor \\[3ex] q \:is\: the\: quotient \\[3ex] r \:is\: the\: remainder $

The Division Algorithm

$a = b * q + r$
Dividend = Divisor * Quotient + Remainder

In Modular Arithmetic;
The dividend can be zero, positive or negative
The divisor must be positive.
The quotient can be zero, positive or negative.
The remainder must always be nonnegative (zero and positive)
If the remainder is negative, we have to manipulate the quotient so we have a positive remainder.
In most cases, we subtract $1$ from the quotient, so that we can get a positive remainder.

$5 | 12 = 2 \:R\: 2$ (positive quotient, positive remainder). No problem
Check: $12 = 5 * 2 + 2$
$\therefore 12 \mod 5 = 2$
Are you seeing the connections?

$9$ divided by $5$ means $5$ divides $9$
$9 \div 5$ means $5 | 9$

$5$ divides $9$ gives $1$ remainder $4$
$5 | 9 = 1 \;\;r\;\; 4$
This is because: $9 = 5 * 1 + 4$
Divisor = $5$
Dividend = $9$
Quotient = $1$
Remainder = $4$
(Not a problem because the divisor and the remainder is positive)

$5 | -9 = -1 \;\;r\;\; -4$
Because: $-9 = 5 * -1 + -4$
Divisor = $5$ (No problem)
Remainder = $-4$ (This is a problem)
So, ask yourself: How can I get a positive remainder even if I have to mess with the quotient? (Yes the quotient can be negative. But the remainder must not be negative)
So, what you need to do is to subtract 1 from the quotient and try to find out the remainder.
Quotient = $-1$
Subtract $1$ from the Quotient
$Quotient = -1 - 1 = -2$
Let the remainder = $r$

$ -9 = 5 * -2 + r \\[3ex] -9 = -10 + r \\[3ex] -9 + 10 = r \\[3ex] 1 = r \\[3ex] r = 1 \\[3ex] \therefore -9 = 5 * -2 + 1 \\[3ex] $ Remainder = $1$ (no problem)
This implies that $-9 \mod 5 = 1$

Another Example:
$10 | -218 = -21\;\;r\;\; -8$
Because $-218 = 10 * -21 + -8$
Remainder = $-8$ (This is a problem)
Quotient = $-21$
Subtract $1$ from the Quotient
$-21 - 1 = -22$
Let the remainder = $r$

$ -218 = 10 * -22 + r \\[3ex] -218 = -220 + r \\[3ex] -218 + 220 = r \\[3ex] 2 = r \\[3ex] r = 2 \\[3ex] \therefore -218 = 10 * -21 + 2 \\[3ex] $ Remainder = $2$ (No problem)
This implies that $-218 \mod 10 = 2$

Equations Involving Modulo (Positive and Negative Values of the Variable)
$\boldsymbol{Example\:1}$: If $X \mod 5 = 1$
$(a.)$ Find the first positive value of $X$
$(b.)$ Find the first negative value of $X$
$(c.)$ Write the positive congruence class of $X \mod 5$
$(d.)$ Write the negative congruence class of $X \mod 5$

Solution
First Step: For the positive values of $X$; Add $1$ and $5$

$ 1 + 5 = 6 \\[3ex] X = 6 \\[3ex] $ Second Step: Keep adding $5$ to your results

$ 6 + 5 = 11 \\[3ex] 11 + 5 = 16 \\[3ex] 16 + 5 = 21 \\[3ex] Positive\:\:Congrence\:\:Class = \{6, 11, 16, 21, ...\} \\[3ex] \underline{Check} \\[3ex] 6\mod 5 = 1 \\[3ex] 11\mod 5 = 1 \\[3ex] 16\mod 5 = 1 \\[3ex] $ This gives an Arithmetic Sequence.
Recall: The $nth$ term of an Arithmetic Sequence

$ AS_n = a + d(n - 1) \\[3ex] where \\[3ex] AS_n = nth\:\:term = Positive\:\:Congruence\:\:Class \\[3ex] a = first\:\:term = 6 \\[3ex] d = common\:\:difference = 5 \\[3ex] n \:\:is\:\:any\:\:positive\:\:integer \\[3ex] \therefore Positive\:\:Congrence\:\:Class = 6 + 5n; \:\:n \epsilon Z_+ \\[3ex] $ Third Step: For the negative values of $X$; Subtract $1$ and $5$

$ 1 - 5 = -4 \\[3ex] X = -4 \\[3ex] $ Fourth Step: Keep subtracting $5$ from your results

$ -4 - 5 = -9 \\[3ex] -9 - 5 = -14 \\[3ex] -14 - 5 = -19 \\[3ex] Negative\:\:Congrence\:\:Class = \{-4, -9, -14, -19, ...\} \\[3ex] \underline{Check} \\[3ex] -4\mod 5 = 1 \\[3ex] -9\mod 5 = 1 \\[3ex] -14\mod 5 = 1 \\[3ex] $ This gives an Arithmetic Sequence.
Recall: The $nth$ term of an Arithmetic Sequence

$ AS_n = a + d(n - 1) \\[3ex] where \\[3ex] AS_n = nth\:\:term = Negative\:\:Congruence\:\:Class \\[3ex] a = first\:\:term = -4 \\[3ex] d = common\:\:difference = -5 \\[3ex] n \:\:is\:\:any\:\:negative\:\:integer \\[3ex] \therefore Negative\:\:Congrence\:\:Class = -4 - 5n; \:\:n \epsilon Z_- \\[3ex] $ Modulo Tables
Let us draw Modulo $5$ Addition Table and Modulo $5$ Multiplication Table
Remember: In Modulo $5$; only numbers $0, 1, 2, 3, 4$ are allowed.

$ Examples\:\: 4 + 4 = 8 \\[3ex] 8\mod 5 = 3 \\[3ex] \therefore (4 + 4)\mod 5 = 3 \\[3ex] 4 * 4 = 16 \\[3ex] 16\mod 5 = 1 \\[3ex] \therefore (4 * 4)\mod 5 = 1 $

Greatest Common Divisor (GCD)

This is also known as HCF (Highest Common Factor) or GCM (Greatest Common Measure)
It is a divisor of two or more positive integers.
This means that it is a factor of two or more positive integers.
This means that it can divide two or more positive integers without a remainder.
It is a common divisor of two or more positive integers.
It is the greatest common divisor of two or more positive integers.
There may be other common divisors of two or more positive integers. However, we are interested in the greatest of those divisors.
Greatest Common Divisor is defined as the greatest positive integer that can divide a set of integers without a remainder.
Say you have two positive integers, $a$ and $b$;
the greatest common divisor of $a$ and $b$ is represented as: $gcd(a, b)$
and it is defined as the greatest positive integer that can divide $a$ and $b$ without a remainder.
NOTE: $1$ is a common factor of every positive integer.

Why Learn GCD?
It is used in cryptology - for secured communications.

There are five methods of calculating the $gcd$ of two or more positive integers.
They are:

(1.) Listing Method: can calculate the $gcd$ of two or more positive integers.
This method is not recommended for a set of big positive integers.

(2.) "Nigerian" Method: (hmmm... I learned this method in the elementary school in Nigeria. I have forgotten the name of the method. It works!) - can calculate the $gcd$ of two or more positive integers.
This method is not recommended for a set of big positive integers.

(3.) Prime Factorization Method: can calculate the $gcd$ of two or more positive integers.
This method is moderate for a set of big positive integers.

(4.) Euclidean Algorithm Method: can calculate the $gcd$ of two positive integers.
This method is recommended for a set of two integers however small or big.

(5.) Extended Euclidean Algorithm Method: can calculate the $gcd$ of two or more positive integers.
This method is recommended for a set of two integers however small or big.

Ask students if they can come up with their own methods after they learn all the five methods.
Encourage them to do so.
Emphasize the importance of life-long learning.
Briefly discuss the discoveries made by other humans which are beneficial to them.
So, why not discover something that will be beneficial to others?
Emphasize the required application of talents given to each of them by GOD.
Use those talents to help one another.

We shall discuss the first three methods in this section.
For the last two methods, please review their respective sections.

Listing Method
In this method; we list all the factors of each positive integer.
We write the common factors of all of them.
Then, we find the greatest common factor of all of them.

An advice:
Begin with $1$, and continue listing the factors in ascending order (from least to greatest).
$1$ is a factor of every positive integer.
Then; as you write any small factor, write the other factor as well (in a separate place).
That way, you would not forget any factor(s).

(1.) Calculate the $gcd$ of $12$ and $18$
Factors of $12 = 1, 2, 3, 4, 6, 12$
Factors of $18 = 1, 2, 3, 6, 9, 18$
Common Factors of $12 \:and\: 18 = 1, 2, 3, 6$
Highest Common Factor of $12 \:and\: 18 = 6$
$gcd(12, 18) = 6$

(2.) Calculate the $gcd$ of $30$ and $105$
Divisors of $30 = 1, 2, 3, 5, 6, 10, 15, 30$
Divisors of $105 = 1, 3, 5, 7, 15, 21, 35, 105$
Common Divisors of $30 \:and\: 105 = 1, 3, 5, 15$
Greatest Common Divisor of $30 \:and\: 105 = 15$
$gcd(30, 105) = 15$

Nigerian Method
In this method; we set up a table of the positive integers.
We set it up the same way we set up the dividend and divisor in the Long Division method of dividing polynomials.
We "try" each factor in ascending order (from least to greatest).
The factor should be a positive integer that has to divide "all" the positive integers without a remainder.
But, if we find another factor of all the integers (a number that divides all the integers "right away" without a remainder), use it.
In other words, it has to be a common factor.
If we cannot find any factor, then the $GCF = 1$.
Remember that $1$ is the smallest factor of every positive integer.
If we find a factor of all the integers (besides $1$), use it. Begin in ascending order.
Multiply all the factors you listed.
The product gives you the $GCF$.

Let us see how this works!
(1.) Calculate the $GCF$ of $12$ and $18$

$ \begin{array}{c|c c} 2 & 12 & 18 \\ \hline 3 & 6 & 9 \\ \hline & 2 & 3 \end{array} \\[3ex] $ We can not find any common factor of $2$ and $3$
STOP.
The factors listed are $2$ and $3$
Multiply them.
$GCF(12, 18) = 2 * 3 = 6$

(2.) Calculate the $gcd$ of $30$ and $105$

$ \begin{array}{c|c c} 3 & 30 & 105 \\ \hline 5 & 10 & 35 \\ \hline & 2 & 7 \end{array} \\[3ex] $ We can not find any common factor of $2$ and $7$
STOP.
The factors listed are $3$ and $5$
Multiply them.
$GCF(30, 105) = 3 * 5 = 15$

Euclidean Algorithm

Modular Inverse

We shall calculate the inverse of a positive integer modulo another positive integer.
To find an inverse, we are "technically" doing a reverse operation.

Bring it to Algebra.
Ask students if they still remember how to find the inverse of a function.
Does every function have an inverse?
What type of function: has an inverse? does not have an inverse?

Every positive integer modulo another positive integer does not have an inverse.
Some do. Some do not.
For a positive integer modulo another positive integer to have an inverse, the two positive integers must be relatively prime.
This means that the greatest common divisor, $gcd$ of the two positive integers must be $1$
We have to make sure that the two positive integers are relatively prime first.
In other words, we have to calculate the $gcd$ of the two positive integers first.
If the $gcd = 1$, then we know that the two positive integers are relatively prime.
Then, we can go ahead and calculate the inverse of one modulo another one.

Recall: Division Algorithm
$a = bq + r$
where:
$a = dividend$
$b = divisor$
$q = quotient$
$r = remainder$

$a \:and\: b$ are positive integers; where $a \gt b$
$a$ should always be the bigger positive integer.
$b$ should always be the smaller positive integer.
$q$ is any negative or positive integers (excludes $0$)
$gcd(a, b) = gcd(b, r)$

Why do we need to calculate an Inverse?
(1.) Because of Bezout's Theorem
The greatest common divisor of two positive integers say $a$ and $b$ can be expressed as a linear combination of $a$ and $b$
Given: two positive integers, $a$ and $b$;
$gcd(a, b) = ma + nb$
where
$m$ and $n$ are the Bezout's coefficients.
$gcd(a, b) = ma + nb$ is known as the Bezout's Identity.

For we to express the $gcd$ of $a$ and $b$ as a linear combination of $a$ and $b$; we have to work in reverse order.
Working in reverse order leads us to calculate the inverse of one positive integer modulo another positive integer.

Example $1$
Calculate the inverse of $4 \mod 9$
First: Calculate the $gcd$ of $4 \:and\: 9$

$ gcd(4, 9) \\[3ex] = gcd(9, 4) \\[3ex] 9 = 4 * 2 + 1 \\[3ex] 4 = 1 * 4 + 0 \\[3ex] \therefore gcd(9, 4) = 1 \\[3ex] $ We have verified that $4$ and $9$ are relatively prime because the $gcd(9, 4) = 1$
How do we express $1$ as a linear combination of $4$ and $9$.
We have to do a reverse process. We have to work backwards.

$ $gcd(a, b) = ma + nb$
gcd(9, 4) = m * 9 + n * 4
1 = 9 - 4 * 2
Remember

Extended Euclidean Algorithm

This method is great!
We can use it to calculate the:
(1.) Greatest Common Divisor
(2.) Bezout's coefficients
(3.) Modular Inverse

Recall: Division Algorithm
$a = bq + r$
where:
$a = dividend$
$b = divisor$
$q = quotient$
$r = remainder$

$a \:and\: b$ are positive integers; where $a \gt b$
$a$ should always be the bigger positive integer.
$b$ should always be the smaller positive integer.
$q$ is any negative or positive integers (excludes $0$)
$r = a - bq$
$gcd(a, b) = ma + nb$ where $m \:and\: n $ are the Bezout's coefficients

We shall use the same examples we used for the Modular Inverse
We shall introduce two new variables $c$ and $d$
We shall list the Steps and follow the directions in the steps in order.

Example $1$

$ inverse\:\:of\;\;4 \mod 9 \\[3ex] a = 9 \\[3ex] b = 4 \\[3ex] $ Step 1
Given: $a = bq + r$
We know that: $a$ = larger positive integer, and $b$ = smaller positive integer
Let $c$ = $a$ = larger positive integer and
Let $d$ = $b$ = smaller positive integer
Let $c = 9\;\;d = 4$

Step 2
Use the Division Algorithm to find the quotient, $q$; and the remainder, $r$.
Then, express $r$ in terms of $a$ and $b$

$ a = bq + r \\[3ex] r = a - bq \\[3ex] r = a - qb \\[3ex] But,\;\; c = a \;\;and\;\; d = b \\[3ex] c = dq + r \\[3ex] r = c - dq \\[3ex] $ In this case (For Extended Euclidean Algorithm Method); it is better to write as $qd$ rather than $dq$
Besides, $dg$ = $qd$ anyway. (Commutative Property of Multiplication)

$ r = c - qd \\[3ex] 9 = 4 * 2 + 1 \\[3ex] 9 = 2 * 4 + 1 \\[3ex] 1 = 9 - 2 * 4 \\[3ex] $ We then have to express it in terms of $a$ and $b$
Remember (Original):

$ a = 9 \;\; b = 4 \\[3ex] 1 = a - 2b ...eqn.(1) \\[3ex] $ Let us call that our Equation (1)

Step 3
If $r \ne 0$, replace $c$ and $d$ with $d$ and $r$ respectively
Then, go back to Step 2
Repeat this process until $r = 0$

$ Remember \;\;that\;\; gcd(a, b) = gcd(b, r) \\[3ex] From\;\; 1 = 9 - 2 * 4 \\[3ex] r = c - qd \\[3ex] r = 1 \\[3ex] c = 9 \\[3ex] d = 4 \\[3ex] q = 2 \\[3ex] $ Replace $c$ and $d$ with $d$ and $r$ respectively

$ c = 4 \\[3ex] d = 1 \\[3ex] $ Go back to Step 2

$ c = dq + r \\[3ex] For\;\; (c, d) = (4, 1) \\[3ex] 4 = 1 * 4 + 0 \\[3ex] r = 0 \\[3ex] $ Stop.
Express $r$ in terms of $a$ and $b$

$ r = c - qd \\[3ex] 0 = 4 - 4 * 1 \\[3ex] Remember\; (Original)\;\; a = 9;\;\; b = 4 \\[3ex] From\;\;Equation (1.) \\[3ex] 1 = a - 2b ...eqn(1) \\[3ex] Substitute\;\; a - 2b \;\;for\;\; 1 \\[3ex] 0 = 4 - 4(a - 2b) \\[3ex] 0 = 4 - 4a + 8b \\[3ex] 0 = b - 4a + 8b \\[3ex] 0 = -4a + 9b \\[3ex] $ Check to see if you are on the right track
At the Conclusion of Step 3 (where the remainder is $0$); you must see $a$ and $b$
$a$ will be in one term, and $b$ will be in the other term.
One term must have a negative value, and the other term must have a positive value.
This is necessary so that when the values of $a$ and $b$ are substituted in that last expression, the remainder is $0$

Step 4
If $r = 0$,
$gcd = d$
Linear combination = previous expression of $r$

$d = 1$
$\therefore gcd(a, b) = 1$
Then, you can express it as a linear combination

$ 1 = a - 2b \\[3ex] 1 = 9 - 2 * 4 \\[3ex] Remember\;\; gcd(a, b) = ma + nb \\[3ex] 1 = 1 * 9 - 2 * 4 \\[3ex] 1 = 1 * 9 + -2 * 4 \\[3ex] $ $9$ and $4$ are the two integers.
$1$ and $-2$ are the Bezout's coefficients
$m = 1$; $n = -2$
The inverse of $4 \mod 9 = -2 \mod 9 = 7$
Remember: the inverse cannot be a negative number.

We can write these steps in a table.

Linear Congruence

System of Linear Congruences

A system of linear congruence is a set of several linear congruences (more than one linear congruence).

It can be solved by:
(1.) The Chinese Remainder Theorem
(2.) The Back Substitution Method

NOTE: We shall be solving a system of linear congruences with relatively prime moduli
Relatively Prime Moduli means that the greatest common divisor of all the moduli is $\boldsymbol{1}$

The Chinese Remainder Theorem

Given a system of linear congruence:

$ x \equiv a_1 \mod m_1 \\[3ex] x \equiv a_2 \mod m_2 \\[3ex] x \equiv a_3 \mod m_3 \\[3ex] . \\[3ex] . \\[3ex] . \\[3ex] x \equiv a_n \mod m_n \\[3ex] $ where:

$m_1, m_2, m_3, ..., m_n$ are relatively prime, and are also positive integers greater than $1$
$a_1, a_2, a_3, ..., a_n$ are positive integers

then there exists:

$ (1.)\:\: M = m_1 * m_2 * m_3 * ... * m_n \\[3ex] (2.)\:\: 0 \le x \lt M \\[3ex] (3.)\:\: other\:\:congruence\:\:classes\:\: x \mod M \\[3ex] $ $\boldsymbol{Example\:1}$: When a positive integer is divided by $5$, the remainder is $4$
When that integer is divided by $7$, the remainder is $6$
Determine the integer.
Determine all other applicable integers.

This can be written as:

$ x \equiv 4 \mod 5 \\[3ex] x \equiv 6 \mod 7 \\[3ex] a_1 = 4 \:\:\:\:\:\:\:\:\:\: a_2 = 6 \\[3ex] m_1 = 5 \:\:\:\:\:\:\:\:\:\: m_2 = 7 \\[3ex] M = m_1 * m_2 \\[3ex] M = 5 * 7 \\[3ex] M = 35 \\[3ex] M_1 = \dfrac{M}{m_1} \:\:\:\:\:\:\:\:\:\: M_2 = \dfrac{M}{m_2} \\[5ex] M_1 = \dfrac{35}{5} \:\:\:\:\:\:\:\:\:\: M_2 = \dfrac{35}{7} \\[5ex] M_1 = 7 \:\:\:\:\:\:\:\:\:\:\:\:\:\: M_2 = 5 \\[3ex] Let\:\: y_1 = inverse\:\:of\:\:M_1 \mod m_1 \\[3ex] y_1 = inverse\:\:of\:\:7 \mod 5 \\[3ex] 7 = 5 * 1 + 2 \\[3ex] 5 = 2 * 2 + 1 \\[3ex] \underline{2 = 1 * 2 + 0} \\[3ex] 1 = 5 - 2 * 2 \\[3ex] = 5 - (7 - 5 * 1)(2) \\[3ex] = 5 - 7(2) + 5(1)(2) \\[3ex] = 5(1) + 5(2) - 7(2) \\[3ex] = 5(1 + 2) - 7(2) \\[3ex] = 5(3) + 7(-2) \\[3ex] inverse\:\:of\:\:7 \mod 5 = -2 \mod 5 = 3 \\[3ex] y_1 = 3 \\[3ex] Let\:\: y_2 = inverse\:\:of\:\:M_2 \mod m_2 \\[3ex] y_2 = inverse\:\:of\:\:5 \mod 7 \\[3ex] inverse\:\:of\:\:5 \mod 7 = 3 \\[3ex] y_2 = 3 \\[3ex] x = (a_1M_1y_1 + a_2M_2y_2) \mod M \\[3ex] x = [4(7)(3) + 6(5)(3)] \mod 35 \\[3ex] x = (84 + 90) \mod 35 \\[3ex] x = 174 \mod 35 \\[3ex] x = 34 \\[3ex] \underline{Check} \\[3ex] 34 \equiv 4 \mod 5 \\[3ex] 34 \equiv 6 \mod 7 \\[3ex] $ Other applicable integers are the congruence class of 34 \mod 35
They are: $69, 104, 139$ among others

$\boldsymbol{Example\:2}$: A positive integer gives a remainder of $2$ when divided by $7$, a remainder of $3$ when divided by $9$, and a remainder of $5$ when divided by $10$
Determine the integer.

This can be written as:

$ x \equiv 2 \mod 7...cong.(1) \\[3ex] x \equiv 3 \mod 9...cong.(2) \\[3ex] x \equiv 5 \mod 10...cong.(3) \\[3ex] a_1 = 2 \\[3ex] a_2 = 3 \\[3ex] a_3 = 5 \\[3ex] m_1 = 7 \\[3ex] m_2 = 9 \\[3ex] m_3 = 10 \\[3ex] M = m_1 * m_2 * m_3 \\[3ex] M = 7 * 9 * 10 \\[3ex] M = 630 \\[3ex] M_1 = \dfrac{M}{m_1} = \dfrac{630}{7} = 90 \\[5ex] M_2 = \dfrac{M}{m_2} = \dfrac{630}{9} = 70 \\[5ex] M_3 = \dfrac{M}{m_3} = \dfrac{630}{10} = 63 \\[5ex] Let\:\: y_1 = inverse\:\:of\:\:M_1 \mod m_1 \\[3ex] y_1 = inverse\:\:of\:\:90 \mod 7 \\[3ex] gcd(90, 7) \\[3ex] 90 = 7 * 12 + 6 \\[3ex] 7 = 6 * 1 + 1 \\[3ex] \underline{6 = 1 * 6 + 0} \\[3ex] 1 = 7 - 6 * 1 \\[3ex] = 7 - (90 - 7 * 12)(1) \\[3ex] = 7 - 90(1) + 7(12)(1) \\[3ex] = 7(1) + 7(12) - 90(1) \\[3ex] = 7(1 + 12) - 90(1) \\[3ex] = 7(13) + 90(-1) \\[3ex] inverse\:\:of\:\:90 \mod 7 = -1 \mod 7 = 6 \\[3ex] y_1 = 6 \\[3ex] Let\:\: y_2 = inverse\:\:of\:\:M_2 \mod m_2 \\[3ex] y_2 = inverse\:\:of\:\:70 \mod 9 \\[3ex] gcd(70, 9) \\[3ex] 70 = 9 * 7 + 7 \\[3ex] 9 = 7 * 1 + 2 \\[3ex] 7 = 2 * 3 + 1 \\[3ex] \underline{2 = 1 * 2 + 0} \\[3ex] 1 = 7 - 2 * 3 \\[3ex] = 7 - (9 - 7 * 1)(3) \\[3ex] = 7(1) - 9(3) + 7(1)(3) \\[3ex] = 7(1) + 7(3) - 9(3) \\[3ex] = 7(1 + 3) - 9(3) \\[3ex] = 7(4) - 9(3) \\[3ex] = (70 - 9 * 7)(4) - 9(3) \\[3ex] = 70(4) - 9(7)(4) - 9(3) \\[3ex] = 70(4) - 9(28) - 9(3) \\[3ex] = 70(4) - 9(28 + 3) \\[3ex] = 70(4) - 9(31) \\[3ex] = 70(4) + 9(-31) \\[3ex] inverse\:\:of\:\:70 \mod 9 = 4 \\[3ex] y_2 = 4 \\[3ex] Let\:\: y_3 = inverse\:\:of\:\:M_3 \mod m_3 \\[3ex] y_3 = inverse\:\:of\:\:63 \mod 10 \\[3ex] gcd(63, 10) \\[3ex] 63 = 10 * 6 + 3 \\[3ex] 10 = 3 * 3 + 1 \\[3ex] \underline{3 = 1 * 3 + 0} \\[3ex] 1 = 10 - 3 * 3 \\[3ex] = 10 - (63 - 10 * 6)(3) \\[3ex] = 10(1) - 63(3) + 10(6)(3) \\[3ex] = 10(1) + 10(18) - 63(3) \\[3ex] = 10(1 + 18) + 63(-3) \\[3ex] = 10(19) + 63(-3) \\[3ex] inverse\:\:of\:\:63 \mod 10 = -3 \mod 10 = 7 \\[3ex] y_3 = 7 \\[3ex] x = (a_1M_1y_1 + a_2M_2y_2 + a_3M_3y_3) \mod M \\[3ex] x = [2(90)(6) + 3(70)(4) + 5(63)(7)] \mod 630 \\[3ex] x = (1080 + 840 + 2205) \mod 630 \\[3ex] x = 4125 \mod 630 \\[3ex] x = 345 \\[3ex] \underline{Check} \\[3ex] 345 \equiv 2 \mod 7 \\[3ex] 345 \equiv 3 \mod 9 \\[3ex] 345 \equiv 5 \mod 10 $

The Back Substitution Method

Given a linear congruence:

$x \equiv a \mod m$

We can convert it to an equation as:

$ x - a = m \\[3ex] This\:\:also\:\:implies\:\:that \\[3ex] x - a = pm \:\:where\:\:p\:\:is\:\:any\:\:positive\:\:integer\:\:greater\:\:than\:\: 1 \\[3ex] x = pm + a \\[3ex] $ We can use algebraic substitution and get the value of $x$
Let us do the same examples we did with the Chinese Remainder Theorem

$\boldsymbol{Example\:1}$: When a positive integer is divided by $5$, the remainder is $4$
When that integer is divided by $7$, the remainder is $6$
Determine the integer.
Determine all other applicable integers.

This can be written as:

$ x \equiv 4 \mod 5...cong.(1) \\[3ex] x \equiv 6 \mod 7...cong.(2) \\[3ex] From\:\:cong.\:\:(1) \\[3ex] x \equiv 4 \mod 5 \\[3ex] x - 4 = 5 \\[3ex] x - 4 = 5p \:\:where\:\:p\gt 1 \\[3ex] x = 5p + 4...eqn.(1) \\[3ex] Subst.\:\:(5p + 4)\:\:for\:\:x\:\:in\:\:cong.(2) \\[3ex] x \equiv 6 \mod 7 \\[3ex] 5p + 4 \equiv 6 \mod 7 \\[3ex] 5p \equiv (6 - 4) \mod 7 \\[3ex] 5p \equiv 2 \mod 7 \\[3ex] $ Find the inverse of $5 \mod 7$

$ gcd(5, 7) = gcd(7, 5) \\[3ex] 7 = 5 * 1 + 2 \\[3ex] 5 = 2 * 2 + 1 \\[3ex] \underline{2 = 1 * 2 + 0} \\[3ex] 1 = 5 - 2 * 2 \\[3ex] = 5 - (7 - 5 * 1)(2) \\[3ex] = 5 - 7(2) + 5(1)(2) \\[3ex] = 5(1) + 5(2) - 7(2) \\[3ex] = 5(1 + 2) - 7(2) \\[3ex] = 5(3) + 7(-2) \\[3ex] inverse\:\:of\:\:5 \mod 7 = 3 \\[3ex] Multiply\:\:both\:\:congruences\:\:by\:\:3 \\[3ex] For\:\: \\[3ex] 5p \equiv 2 \mod 7 \\[3ex] 3 * 5 * p \equiv 3 * 2 \mod 7 \\[3ex] 15 * p \equiv 6 \mod 7 \\[3ex] \rightarrow 15 \mod 7 * p \mod 7 \equiv 6 \mod 7 \\[3ex] 15 \mod 7 = 1 \\[3ex] p \mod 7 = p \mod 7 \\[3ex] 6 \mod 7 = 6 \\[3ex] \rightarrow 1 * p \mod 7 \equiv 6 \\[3ex] p \mod 7 \equiv 6 \\[3ex] p = 6 ...eqn.(2) \\[3ex] Subst.\:\:6\:\:for\:\:p\:\:in\:\:eqn.(1) \\[3ex] x = 5p + 4 \\[3ex] x = 5 * 6 + 4 \\[3ex] x = 30 + 4 \\[3ex] x = 34 \\[3ex] \underline{Check} \\[3ex] 34 \equiv 4 \mod 5 \\[3ex] 34 \equiv 6 \mod 7 \\[3ex] $ To find other applicable integers; first: multiply the two moduli
Product = $5 * 7 = 35$
Other applicable integers are the congruence class of 34 \mod 35
They are: $69, 104, 139$ among others

$\boldsymbol{Example\:2}$: A positive integer gives a remainder of $2$ when divided by $7$, a remainder of $3$ when divided by $9$, and a remainder of $5$ when divided by $10$
Determine the integer.

This can be written as:

$ x \equiv 2 \mod 7...cong.(1) \\[3ex] x \equiv 3 \mod 9...cong.(2) \\[3ex] x \equiv 5 \mod 10...cong.(3) \\[3ex] From\:\:cong.\:\:(1) \\[3ex] x \equiv 2 \mod(7) \\[3ex] x - 2 = 7 \\[3ex] x - 2 = 7p \:\:where\:\:p\gt 1 \\[3ex] x = 7p + 2...eqn.(1) \\[3ex] Subst.\:\:(7p + 2)\:\:for\:\:x\:\:in\:\:cong.(2) \\[3ex] x \equiv 3 \mod 9 \\[3ex] 7p + 2 \equiv 3 \mod 9 \\[3ex] 7p \equiv (3 - 2) \mod 9 \\[3ex] 7p \equiv 1 \mod 9 \\[3ex] $ Find the inverse of $7 \mod 9$

$ gcd(7, 9) = gcd(9, 7) \\[3ex] 9 = 7 * 1 + 2 \\[3ex] 7 = 2 * 3 + 1 \\[3ex] \underline{2 = 1 * 2 + 0} \\[3ex] 1 = 7 - 2 * 3 \\[3ex] = 7 - (9 - 7 * 1)(3) \\[3ex] = 7 - 9(3) + 7(1)(3) \\[3ex] = 7(1) + 7(3) - 9(3) \\[3ex] = 7(1 + 3) - 9(3) \\[3ex] = 7(4) + 9(-3) \\[3ex] inverse\:\:of\:\:7 \mod 9 = 4 \\[3ex] Multiply\:\:both\:\:congruences\:\:by\:\:4 \\[3ex] For\:\: \\[3ex] 7p \equiv 1 \mod 9 \\[3ex] 4 * 7 * p \equiv 4 * 1 \mod 9 \\[3ex] 28 * p \equiv 4 \mod 9 \\[3ex] \rightarrow 28 \mod 9 * p \mod 9 \equiv 4 \mod 9 \\[3ex] 28 \mod 9 = 1 \\[3ex] p \mod 9 = p \mod 9 \\[3ex] 4 \mod 9 = 4 \\[3ex] \rightarrow 1 * p \mod 9 \equiv 4 \\[3ex] p \mod 9 \equiv 4 \\[3ex] p = 4 \\[3ex] $ However, we shall not substitute right away because we have not used $cong. (3)$
We have to use all congruences
So, we need to find another variable

$ p = 4 \\[3ex] p \equiv 4 \mod 9 \\[3ex] p - 4 = 9 \\[3ex] p - 4 = 9k \:\:where\:\:k\gt 1 \\[3ex] p = 9k + 4 \\[3ex] p = 9k + 4...eqn.(2) \\[3ex] Subst.\:\:(9k + 4)\:\:for\:\:p\:\:in\:\:eqn.(1) \\[3ex] x = 7p + 2 \\[3ex] x = 7(9k + 4) + 2 \\[3ex] x = 63k + 28 + 2 \\[3ex] x = 63k + 30...eqn.(3) \\[3ex] Subst.\:\:(63k + 30)\:\:for\:\:x\:\:in\:\:cong.(3) \\[3ex] x \equiv 5 \mod 10 \\[3ex] 63k + 30 \equiv 5 \mod 10 \\[3ex] 63k \equiv (5 - 30) \mod 10 \\[3ex] 63k \equiv -25 \mod 10 \\[3ex] $ Find the inverse of $63 \mod 10$

$ gcd(63, 10) \\[3ex] 63 = 10 * 6 + 3 \\[3ex] 10 = 3 * 3 + 1 \\[3ex] \underline{3 = 1 * 3 + 0} \\[3ex] 1 = 10 - 3 * 3 \\[3ex] = 10 - (63 - 10 * 6)(3) \\[3ex] = 10(1) - 63(3) + 10(6)(3) \\[3ex] = 10(1) + 10(18) - 63(3) \\[3ex] = 10(1 + 18) + 63(-3) \\[3ex] = 10(19) + 63(-3) \\[3ex] inverse\:\:of\:\:63 \mod 10 = -3 \mod 10 = 7 \\[3ex] Multiply\:\:both\:\:congruences\:\:by\:\:7 \\[3ex] For\:\: \\[3ex] 63k \equiv -25 \mod 10 \\[3ex] 7 * 63 * k \equiv 7 * -25 \mod 10 \\[3ex] 441 * k \equiv -175 \mod 10 \\[3ex] \rightarrow 441 \mod 10 * k \mod 10 \equiv -175 \mod 10 \\[3ex] 441 \mod 10 = 1 \\[3ex] k \mod 10 = k \mod 10 \\[3ex] -175 \mod 10 = 5 \\[3ex] \rightarrow 1 * k \mod 10 \equiv 5 \\[3ex] k \mod 10 \equiv 5 \\[3ex] k = 5 ...eqn.(3) \\[3ex] Subst.\:\:5\:\:for\:\:k\:\:in\:\:eqn.(3) \\[3ex] x = 63k + 30 \\[3ex] x = 63 * 5 + 30 \\[3ex] x = 315 + 30 \\[3ex] x = 345 \\[3ex] \underline{Check} \\[3ex] 345 \equiv 2 \mod 7 \\[3ex] 345 \equiv 3 \mod 9 \\[3ex] 345 \equiv 5 \mod 10 \\[3ex] $ NOTE: You always have to use all the congruences.
When you have more than two congruences, do not substitute "finally" until you have used "all" the congruences.
You have to "back-substitute" till the final congrunce and the final equation.

Modular Exponentiation

In Modular Exponentiation, we want to calculate: an integer raised to a nonnegative integer modulo a positive integer.
Say we have: $a^b \mod n$,
$a$ and $b$ are nonnegative integers
$n$ is a positive integer
If $b$ is very large, the calculation of $a^b \mod n$ cannot be done with a calculator.
Hence, we need to find how to solve such calculations.

Why learn Modular Exponentiation?

Modular Exponentiation is one of the concepts used in Cryptology.
Cryptology is the study of writing and cracking secret messages.
Specifically, modular exponentiation is used in the RSA (Rivest, Shamir, Adelman) cryptosystem for secured data transmissions.

There are four methods of solving modular exponentiation.
They are:
(1.) Method of Fast Modular Multiplication
(2.) Method of Repeated Squaring using the Modular Exponentiation Algorithm
(3.) Fermat's Little Theorem
(4.) Fermat's Little Theorem and the Chinese Remainder Theorem

We shall solve two examples using at least three methods.
To see more examples solved by using these methods, please visit: Solved Examples on Modular Exponentiation

First Method: Method of Fast Modular Multiplication
It can solve any modular exponentiation problem.
In the method of Fast Modular Multiplication, a given base with a given exponent modulo a positive integer is broken down into a product of simpler exponents with the same base modulo that integer.
The result of each base with an exponent modulo that integer is calculated.
Those individual results are then multiplied modulo that integer.
The final result is calculated.

Say we need to calculate: $3^7 \mod 5$
$3^1 \mod 5 = 3 \mod 5 = 3$
$3^2 \mod 5 = 9 \mod 5 = 4$
$3^3 \mod 5 = 27 \mod 5 = 2$

But, wait a minute...
Can we calculate $3^3 \mod 5$ another way?
We know that $3^3 = 3^2 * 3^1$
So, $3^3 \mod 5 = ((3^2 \mod 5) * (3^1 \mod 5)) \mod 5$
But $3^2 \mod 5 = 4$
and
$3^1 \mod 5 = 3$
$3^3 \mod 5 = (4 * 3) \mod 5$
$= 12 \mod 5$
$= 2$

Ask students if they understood what you did. Would it be better to do it that way?
If they prefer the first way, $27 \mod 5$, ask them what to do if they encounter "large" product (product of 15 digits or more that can not fit in a scientific calculator).
Note their responses. How many changed their minds?

$3^4 \mod 5 = 81 \mod 5 = 1$
OR
$3^4 \mod 5 = ((3^2 \mod 5) * (3^2 \mod 5)) \mod 5$
$= (3^2 \mod 5)^2 \mod 5$
$= 4^2 \mod 5$
$= 16 \mod 5$
$= 1$

$3^5 \mod 5 = 243 \mod 5 = 3$
OR
$3^5 \mod 5 = ((3^3 \mod 5) * (3^2 \mod 5)) \mod 5$
$= (2 * 4) \mod 5$
$= 8 \mod 5 = 3$
As we move on to larger exponents, the results keep increasing... from $3, 9, 27, 81, 243,...$
Imagine trying to calculate $3^{57} \mod 5$!
Can your calculator compute $3^{57}$?
Hence, the need to break down that exponent into a product of simpler exponents.
Hence, the need for Fast Modular Multiplication!
Let us do more examples.

Example $1:$ Calculate $3^{302} \mod 5$

$1st$ Step: Convert the exponent to a binary base. $$ \begin{array}{c|c} 2 & 302 \\ \hline 2 & 151 \:R\: 0 \\ \hline 2 & 75 \:R\: 1 \\ \hline 2 & 37 \:R\: 1 \\ \hline 2 & 18 \:R\: 1 \\ \hline 2 & 9 \:R\: 0 \\ \hline 2 & 4 \:R\: 1 \\ \hline 2 & 2 \:R\: 0 \\ \hline 2 & 1 \:R\: 0 \\ \hline & 0 \:R\: 1 \end{array} Count \:the\: remainders\: upwards $$ $$ 302 = 100101110_2 $$ $2nd$ Step: Write the place values of the binary digit. $$ \begin{align} 2^8\ \ 2^7\ \ 2^6\ \ 2^5\ \ 2^4\ \ 2^3\ \ 2^2\ \ 2^1\ \ 2^0~~~~~~\ \ \\ 1\ \ \ 0\ \ \ 0\ \ \ \ 1\ \ \ \ 0\ \ \ \ 1\ \ \ \ 1\ \ \ \ 1\ \ \ \ 0~~~~~~\ \ \ \end{align} $$ $3rd$ Step: Simplify. Write the main problem as a product of smaller exponents.

$ 3^{302} = 3^{(1 * 2^8 + 0 * 2^7 + 0 * 2^6 + 1 * 2^5 + 0 * 2^4 + 1 * 2^3 + 1 * 2^2 + 1 * 2^1 + 0 * 2^0)} \\[3ex] = 3^{(1 * 256 + 0 * 128 + 0 * 64 + 1 * 32 + 0 * 16 + 1 * 8 + 1 * 4 + 1 * 2 + 0 * 1)} \\[3ex] = 3^{(256 + 0 + 0 + 32 + 0 + 8 + 4 + 2 + 0)} \\[3ex] Apply \:the\: laws\: of\: exponents...Law\:\:1...Exp \\[3ex] = 3^{256} * 3^0 * 3^0 * 3^{32} * 3^0 * 3^8 * 3^4 * 3^2 * 3^0 \\[3ex] = 3^{256} * 1 * 1 * 3^{32} * 1 * 3^8 * 3^4 * 3^2 * 1 \\[3ex] Going\: forward\:, we\: shall\: forget\: the\: zeros \\[3ex] There\: is\: no\: need\: to\: write\: them \\[3ex] Because\: any\: base\:to\: exponent\: zero\: gives\: 1 \\[3ex] 3^{302} \mod 7 \\[3ex] = (3^{256} * 3^{32} * 3^8 * 3^4 * 3^2) \mod 5 \\[3ex] = 3^{256} \mod 5 * 3^{32} \mod 5 * 3^8 \mod 5 * 3^4 \mod 5 * 3^2 \mod 5 \\[5ex] 3^2 \mod 5 = 9 \mod 5 = \color{red}{4} \\[3ex] 3^4 \mod 5 = (3^2)^2 \mod 5 = (3^2 \mod 5)^2 \mod 5 = 4^2 \mod 5 = 16 \mod 5 = \color{red}{1} \\[3ex] 3^8 \mod 5 = (3^4)^2 \mod 5 = (3^4 \mod 5)^2 \mod 5 = 1^2 \mod 5 = 1 \mod 5 = \color{red}{1} \\[3ex] 3^{32} \mod 5 = (3^8)^2 \mod 5 = (3^8 \mod 5)^2 \mod 5 = 1^2 \mod 5 = 1 \mod 5 = \color{red}{1} \\[3ex] 3^{256} \mod 5 = (3^{32})^8 \mod 5 = (3^{32} \mod 5)^8 \mod 5 = 1^8 \mod 5 = 1 \mod 5 = \color{red}{1} \\[5ex] 3^{302} \mod 5 \\[3ex] = 3^{256} \mod 5 * 3^{32} \mod 5 * 3^8 \mod 5 * 3^4 \mod 5 * 3^2 \mod 5 \\[3ex] = (1 * 1 * 1 * 1 * 4) \mod 5 \\[3ex] = 4 \mod 5 \\[3ex] = 4 \\[3ex] $ $\therefore 3^{302} \mod 5$ = $4$

Example $2:$ Calculate $5^{2003} \mod 7$

$1st$ Step: Convert the exponent to a binary base. $$ \begin{array}{c|c} 2 & 2003 \\ \hline 2 & 1001 \:R\: 1 \\ \hline 2 & 500 \:R\: 1 \\ \hline 2 & 250 \:R\: 0 \\ \hline 2 & 125 \:R\: 0 \\ \hline 2 & 62 \:R\: 1 \\ \hline 2 & 31 \:R\: 0 \\ \hline 2 & 15 \:R\: 1 \\ \hline 2 & 7 \:R\: 1 \\ \hline 2 & 3 \:R\: 1 \\ \hline 2 & 1 \:R\: 1 \\ \hline & 0 \:R\: 1 \end{array} Count \:the\: remainders\: upwards $$ $$ 2003 = 11111010011_2 $$ $2nd$ Step: Write the place values of the binary digit. $$ \begin{align} 2^{10}\ \ 2^9\ \ 2^8\ \ 2^7\ \ 2^6\ \ 2^5\ \ 2^4\ \ 2^3\ \ 2^2\ \ 2^1\ \ 2^0 \\ 1\ \ \ 1\ \ \ 1\ \ \ 1\ \ \ 1\ \ \ \ 0\ \ \ \ 1\ \ \ \ 0\ \ \ \ 0\ \ \ 1\ \ \ 1\ \ \ \end{align} $$ $3rd$ Step: Simplify. Write the main problem as a product of smaller exponents.

$ 5^{2003} \\[3ex] Forget\: the\: zeros \\[3ex] = 5^{(1 * 2^{10} + 1 * 2^9 + 1 * 2^8 + 1 * 2^7 + 1 * 2^6 + 1 * 2^4 + 1 * 2^1 + 1 * 2^0)} \\[3ex] = 5^{(1 * 1024 + 1 * 512 + 1 * 256 + 1 * 128 + 1 * 64 + 1 * 16 + 1 * 2 + 1 * 1)} \\[3ex] = 5^{(1024 + 512 + 256 + 128 + 64 + 16 + 2 + 1)} \\[3ex] Apply \:the\: laws\: of\: exponents...Law\:\:1...Exp \\[3ex] = 5^{1024} * 5^{512} * 5^{256} * 5^{128} * 5^{64} * 5^{16} * 5^2 * 5^1 \\[3ex] 5^{2003} \mod 7 \\[3ex] = (5^{1024} * 5^{512} * 5^{256} * 5^{128} * 5^{64} * 5^{16} * 5^2 * 5^1) \mod 7 \\[3ex] = 5^{1024} \mod 7 * 5^{512} \mod 7 * 5^{256} \mod 7 * 5^{128} \mod 7 * 5^{64} \mod 7 * 5^{16} \mod 7 * 5^2 \mod 7 * 5^1 \mod 7 \\[5ex] 5^1 \mod 7 = 5 \mod 7 = \color{red}{5} \\[3ex] 5^2 \mod 7 = 25\mod 7 = \color{red}{4} \\[3ex] 5^{16} \mod 7 = (5^2)^{8}\mod 7 = 4^8\mod 7 = 65536\mod 7 = \color{red}{2} \\[3ex] 5^{64} \mod 7 = (5^{16})^{4}\mod 7 = 2^4\mod 7 = 16\mod 7 = \color{red}{2} \\[3ex] 5^{128} \mod 7 = (5^{64})^{2}\mod 7 = 2^2\mod 7 = 4\mod 7 = \color{red}{4} \\[3ex] 5^{256} \mod 7 = (5^{128})^{2}\mod 7 = 4^2\mod 7 = 16\mod 7 = \color{red}{2} \\[3ex] 5^{512} \mod 7 = (5^{256})^{2}\mod 7 = 2^2\mod 7 = 4\mod 7 = \color{red}{4} \\[3ex] 5^{1024} \mod 7 = (5^{512})^{2}\mod 7 = 4^2\mod 7 = 16\mod 7 = \color{red}{2} \\[5ex] 5^{2003} \mod 7 \\[3ex] = 5^{1024} \mod 7 * 5^{512} \mod 7 * 5^{256} \mod 7 * 5^{128} \mod 7 * 5^{64} \mod 7 * 5^{16} \mod 7 * 5^2 \mod 7 * 5^1 \mod 7 \\[5ex] = (2 * 4 * 2 * 4 * 2 * 2 * 4 * 5) \mod 7 \\[3ex] = 5120 \mod 7 \\[3ex] = 3 \\[3ex] $ $\therefore 5^{2003} \mod 7$ = $3$



Second Method: Method of Repeated Squaring using the Modular Exponentiation Algorithm
It can solve any modular exponentiation problem.
In the method of Repeated Squaring, the following algorithm is used.

Say you have $a^b \mod n$
Modular Exponentiation Algorithm $(a, b, n)$
(1.) $c = 0$ Initialize
(2.) $d = 1$ Initialize
(3.) Let $\langle b_k, b_{k - 1}, b_{k - 2}, b_{k - 3}, ..., b_0\rangle$ be the binary representation of $b$
(4.) for $i = k$ down to $0$
This means from when $i = k$ to when $i = k - 1$ to when $i = k - 2$....down to when $i = 0$
For each $i$,
(5.) $c = 2c$
(6.) $d = (d * d) \mod n$

But,
(7.) if $b_i == 1$,
(8.) $c = c + 1$
(9.) $d = (d * a) \mod n$

(10.) return $d$

$d$ is the result.

Let us do the same problems we did using the Fast Modular Multiplication.

Example $1:$ Calculate $3^{302} \mod 5$

$1st$ Step: Write the values of $a, b, n$

Compare $3^{302} \mod 5$ to $a^b \mod n$

$ a = 3 \\[3ex] b = 302 \\[3ex] n = 5 \\[3ex] $ $2nd$ Step: Find the binary representation of $b$ $$ \begin{array}{c|c} 2 & 302 \\ \hline 2 & 151 \:R\: 0 \\ \hline 2 & 75 \:R\: 1 \\ \hline 2 & 37 \:R\: 1 \\ \hline 2 & 18 \:R\: 1 \\ \hline 2 & 9 \:R\: 0 \\ \hline 2 & 4 \:R\: 1 \\ \hline 2 & 2 \:R\: 0 \\ \hline 2 & 1 \:R\: 0 \\ \hline & 0 \:R\: 1 \end{array} Count \:the\: remainders\: upwards $$
$302 = \langle 100101110 \rangle$

$3rd$ Step: Form a table and use the Modular Exponentiation algorithm to solve the problem.

$ 302 = \langle 100101110 \rangle \\[3ex] \langle 100101110 \rangle = 100101110_2 \\[3ex] = 1 * 2^8 + 0 * 2^7 + 0 * 2^6 + 1 * 2^5 + 0 * 2^4 + 1 * 2^3 + 1 * 2^2 + 1 * 2^1 + 0 * 2^0 \\[3ex] $ This means that: $i = 8...down\: to\: 0$
$i$ are the exponents.
$b_i$ are the binary representations (the face values).

$ a = 3 \\[3ex] b = 302 \\[3ex] n = 5 \\[3ex] b_8 = 1 \\[3ex] b_7 = 0 \\[3ex] b_6 = 0 \\[3ex] b_5 = 1 \\[3ex] b_4 = 0 \\[3ex] b_3 = 1 \\[3ex] b_2 = 1 \\[3ex] b_1 = 1 \\[3ex] b_0 = 0 \\[3ex] $ Let us do the algorithm step-by-step

Initial: $c = 0$, $d = 1$

For $i = 8$
$b_8 = 1$
$c = 2c$
$c = 2 * 0$
$c = 0$

$d = (d * d) \mod n$
$d = (1 * 1) \mod 5$
$d = 1 \mod 5$
$d = 1$

But $b_8 = 1$
$c = c + 1$
$c = 0 + 1$
$c = 1$

$d = (d * a) \mod n$
$d = (1 * 3) \mod 645$
$d = 3 \mod 645$
$d = 3$

We shall not initial again. The initialization is for the first case.

For $i = 7$
$b_7 = 0$
$c = 2c$
$c = 2 * 1$
$c = 2$

$d = (d * d) \mod n$
$d = (3 * 3) \mod 5$
$d = 9 \mod 5$
$d = 4$

But $b_7 = 0$
Stop.

For $i = 6$
$b_6 = 0$
$c = 2c$
$c = 2 * 2$
$c = 4$

$d = (d * d) \mod n$
$d = (4 * 4) \mod 5$
$d = 16 \mod 5$
$d = 1$

But $b_6 = 0$
Stop.

For $i = 5$
$b_5 = 1$
$c = 2c$
$c = 2 * 4$
$c = 8$

$d = (d * d) \mod n$
$d = (1 * 1) \mod 5$
$d = 1 \mod 5$
$d = 1$

But $b_5 = 1$
$c = c + 1$
$c = 8 + 1$
$c = 9$

$d = (d * a) \mod n$
$d = (1 * 3) \mod 5$
$d = 3 \mod 5$
$d = 3$

For $i = 4$
$b_4 = 0$
$c = 2c$
$c = 2 * 9$
$c = 18$

$d = (d * d) \mod n$
$d = (3 * 3) \mod 5$
$d = 9 \mod 5$
$d = 4$

But $b_4 = 0$
Stop.

For $i = 3$
$b_3 = 1$
$c = 2c$
$c = 2 * 18$
$c = 36$

$d = (d * d) \mod n$
$d = (4 * 4) \mod 5$
$d = 16 \mod 5$
$d = 1$

But $b_3 = 1$
$c = c + 1$
$c = 36 + 1$
$c = 37$

$d = (d * a) \mod n$
$d = (1 * 3) \mod 5$
$d = 3 \mod 5$
$d = 3$

For $i = 2$
$b_2 = 1$
$c = 2c$
$c = 2 * 37$
$c = 74$

$d = (d * d) \mod n$
$d = (3 * 3) \mod 5$
$d = 9 \mod 5$
$d = 4$

But $b_2 = 1$
$c = c + 1$
$c = 74 + 1$
$c = 75$

$d = (d * a) \mod n$
$d = (4 * 3) \mod 5$
$d = 12 \mod 5$
$d = 2$

For $i = 1$
$b_1 = 1$
$c = 2c$
$c = 2 * 75$
$c = 150$

$d = (d * d) \mod n$
$d = (2 * 2) \mod 5$
$d = 4 \mod 5$
$d = 4$

But $b_1 = 1$
$c = c + 1$
$c = 150 + 1$
$c = 151$

$d = (d * a) \mod n$
$d = (4 * 3) \mod 5$
$d = 12 \mod 5$
$d = 2$

For $i = 0$
$b_0 = 0$
$c = 2c$
$c = 2 * 151$
$c = 302$

$d = (d * d) \mod n$
$d = (2 * 2) \mod 5$
$d = 4 \mod 5$
$d = 4$

But $b_0 = 0$
Stop.

Example $2:$ Calculate $5^{2003} \mod 7$

$1^{st}$ Step: Write the values of $a, b, n$

Compare $3^{302} \mod 5$ to $a^b \mod n$

$ a = 5 \\[3ex] b = 2003 \\[3ex] n = 7 \\[3ex] $ $2^{nd}$ Step: Find the binary representation of $b$ $$ \begin{array}{c|c} 2 & 2003 \\ \hline 2 & 1001 \:R\: 1 \\ \hline 2 & 500 \:R\: 1 \\ \hline 2 & 250 \:R\: 0 \\ \hline 2 & 125 \:R\: 0 \\ \hline 2 & 62 \:R\: 1 \\ \hline 2 & 31 \:R\: 0 \\ \hline 2 & 15 \:R\: 1 \\ \hline 2 & 7 \:R\: 1 \\ \hline 2 & 3 \:R\: 1 \\ \hline 2 & 1 \:R\: 1 \\ \hline & 0 \:R\: 1 \end{array} Count \:the\: remainders\: upwards $$
$2003 = \langle 11111010011 \rangle$

$3^{rd}$ Step: Form a table and use the Modular Exponentiation algorithm to solve the problem.

$ 2003 = \langle 11111010011 \rangle \\[3ex] \langle 11111010011 \rangle = 11111010011_2 \\[3ex] = 1 * 2^{10} + 1 * 2^9 + 1 * 2^8 + 1 * 2^7 + 1 * 2^6 + 0 * 2^5 + 1 * 2^4 + 0 * 2^3 + 0 * 2^2 + 1 * 2^1 + 1 * 2^0 \\[3ex] $ This means that: $i = 10...down\: to\: 0$
$i$ are the exponents.
$b_i$ are the binary representations (the face values).

$ a = 5 \\[3ex] b = 2003 \\[3ex] n = 7 \\[3ex] b_{10} = 1 \\[3ex] b_9 = 1 \\[3ex] b_8 = 1 \\[3ex] b_7 = 1 \\[3ex] b_6 = 1 \\[3ex] b_5 = 0 \\[3ex] b_4 = 1 \\[3ex] b_3 = 0 \\[3ex] b_2 = 0 \\[3ex] b_1 = 1 \\[3ex] b_0 = 1 \\[3ex] $ Let us do the algorithm step-by-step

Initial: $c = 0$, $d = 1$

For $i = 10$
$b_{10} = 1$
$c = 2c$
$c = 2 * 0$
$c = 0$

$d = (d * d) \mod n$
$d = (1 * 1) \mod 5$
$d = 1 \mod 5$
$d = 1$

But $b_{10} = 1$
$c = c + 1$
$c = 0 + 1$
$c = 1$

$d = (d * a) \mod n$
$d = (1 * 5) \mod 7$
$d = 5 \mod 7$
$d = 5$

We shall not initial again. The initialization is for the first case.

For $i = 9$
$b_9 = 1$
$c = 2c$
$c = 2 * 1$
$c = 2$

$d = (d * d) \mod n$
$d = (5 * 5) \mod 7$
$d = 25 \mod 7$
$d = 4$

But $b_9 = 1$
$c = c + 1$
$c = 2 + 1$
$c = 3$

$d = (d * a) \mod n$
$d = (4 * 5) \mod 7$
$d = 20 \mod 7$
$d = 6$

For $i = 8$
$b_8 = 1$
$c = 2c$
$c = 2 * 3$
$c = 6$

$d = (d * d) \mod n$
$d = (6 * 6) \mod 7$
$d = 36 \mod 7$
$d = 1$

But $b_8 = 1$
$c = c + 1$
$c = 6 + 1$
$c = 7$

$d = (d * a) \mod n$
$d = (1 * 5) \mod 7$
$d = 5 \mod 7$
$d = 5$

For $i = 7$
$b_7 = 1$
$c = 2c$
$c = 2 * 7$
$c = 14$

$d = (d * d) \mod n$
$d = (5 * 5) \mod 7$
$d = 25 \mod 7$
$d = 4$

But $b_7 = 1$
$c = c + 1$
$c = 14 + 1$
$c = 15$

$d = (d * a) \mod n$
$d = (4 * 5) \mod 7$
$d = 20 \mod 7$
$d = 6$

For $i = 6$
$b_6 = 1$
$c = 2c$
$c = 2 * 15$
$c = 30$

$d = (d * d) \mod n$
$d = (6 * 6) \mod 7$
$d = 36 \mod 7$
$d = 1$

But $b_6 = 1$
$c = c + 1$
$c = 30 + 1$
$c = 31$

$d = (d * a) \mod n$
$d = (1 * 5) \mod 7$
$d = 5 \mod 7$
$d = 5$

For $i = 5$
$b_5 = 0$
$c = 2c$
$c = 2 * 31$
$c = 62$

$d = (d * d) \mod n$
$d = (5 * 5) \mod 7$
$d = 25 \mod 7$
$d = 4$

But $b_5 = 0$
Stop.

For $i = 4$
$b_4 = 1$
$c = 2c$
$c = 2 * 62$
$c = 124$

$d = (d * d) \mod n$
$d = (4 * 4) \mod 7$
$d = 16 \mod 7$
$d = 2$

But $b_4 = 1$
$c = c + 1$
$c = 124 + 1$
$c = 125$

$d = (d * a) \mod n$
$d = (2 * 5) \mod 7$
$d = 10 \mod 7$
$d = 3$

For $i = 3$
$b_3 = 0$
$c = 2c$
$c = 2 * 125$
$c = 250$

$d = (d * d) \mod n$
$d = (3 * 3) \mod 7$
$d = 9 \mod 7$
$d = 2$

But $b_3 = 0$
Stop.

For $i = 2$
$b_2 = 0$
$c = 2c$
$c = 2 * 250$
$c = 500$

$d = (d * d) \mod n$
$d = (2 * 2) \mod 7$
$d = 4 \mod 7$
$d = 4$

But $b_2 = 0$
Stop.

For $i = 1$
$b_1 = 1$
$c = 2c$
$c = 2 * 500$
$c = 1000$

$d = (d * d) \mod n$
$d = (4 * 4) \mod 7$
$d = 16 \mod 7$
$d = 2$

But $b_4 = 1$
$c = c + 1$
$c = 1000 + 1$
$c = 1001$

$d = (d * a) \mod n$
$d = (2 * 5) \mod 7$
$d = 10 \mod 7$
$d = 3$

For $i = 0$
$b_0 = 1$
$c = 2c$
$c = 2 * 1001$
$c = 2002$

$d = (d * d) \mod n$
$d = (3 * 3) \mod 7$
$d = 9 \mod 7$
$d = 2$

But $b_0 = 1$
$c = c + 1$
$c = 2002 + 1$
$c = 2003$

$d = (d * a) \mod n$
$d = (2 * 5) \mod 7$
$d = 10 \mod 7$
$d = 3$

Some students may ask you the purpose of calculating the values of $c$
Ask them if they noticed anything in the last values of $c$ in the two tables.

How do we know we calculated the values of $c$ correctly?
The last value of $c$ should always give you the exponent.
In $a^b \mod n$,
the last value of $c$ should always be equal to the $b$

Ask students if they can use a scientific calculator to check if the values of $d$ are correct

Third Method: Fermat's Little Theorem
This method is attributed to the French Mathematician, Pierre de Fermat.
It can solve certain modular exponentiation problems.
So, what kind of problems can it solve?

$ For\:\:any\:\: a^k \mod p \\[3ex] where \\[3ex] a = base \\[3ex] k = exponent \\[3ex] p = modulo \\[3ex] $ Fermat's Little Theorem
Conditions:
(1.) The modulo must be a prime number
$p \:\:is\:\: prime$

(2.) The base must be an integer not divisible by the modulo.
In other words, the modulo cannot divide the base without a remainder. $p \nmid a$

I shall be adding another condition
(3.) The exponent should be greater than the modulo
$k \gt p$

then:
$ (1.)\:\: a^{p - 1} \equiv 1 \mod p \\[5ex] (2.)\:\: a^p \equiv p \mod p \\[3ex] $ Let us do the same problems we did using the Fast Modular Multiplication and the Modular Exponentiation Algorithm.

Example $1:$ Calculate $3^{302} \mod 5$

$ p = 5 \\[3ex] 5 \:\:is\:\:prime \checkmark \\[3ex] a = 3 \\[3ex] 5 \nmid 3 \checkmark \\[3ex] k = 302 \\[3ex] 302 \gt 5 \checkmark \\[3ex] 3^{5 - 1} \equiv 1 \mod 5 ...Fermat's\:\:Little\:\:Theorem \\[3ex] 3^4 \equiv 1 \mod 5 \\[3ex] Focus\:\:on\:\:the\:\:two\:\:exponents:\:\: 302 \:\:and\:\: 4 \\[3ex] 302 = 4 * 75 + 2 \\[3ex] \rightarrow 3^{302} = 3^{(4 * 75 + 2)} (mod 5) \\[3ex] = (3^{4 * 75} * 3^2) \mod 5 ...Law\:\:1...Exp \\[3ex] = [(3^4)^{75} * 9] \mod 5 \\[3ex] = (3^4)^{75} \mod 5 * 9 \mod 5 \\[3ex] (3^4)^{75} \mod 5 = 1^{75} \mod 5 = 1 \mod 5 = 1 \\[3ex] 9 \mod 5 = 4 \\[3ex] = 1 * 4 \\[3ex] = 4 \\[3ex] $ $\therefore 3^{302} \mod 5$ = $4$

Example $2:$ Calculate $5^{2003} \mod 7$

$ p = 7 \\[3ex] 7 \:\:is\:\:prime \checkmark \\[3ex] a = 5 \\[3ex] 7 \nmid 5 \checkmark \\[3ex] k = 2003 \\[3ex] 2003 \gt 7 \checkmark \\[3ex] 5^{7 - 1} \equiv 1 \mod 7 ...Fermat's\:\:Little\:\:Theorem \\[3ex] 5^6 \equiv 1 \mod 7 \\[3ex] Focus\:\:on\:\:the\:\:two\:\:exponents:\:\: 2003 \:\:and\:\: 6 \\[3ex] 2003 = 6 * 333 + 5 \\[3ex] \rightarrow 5^{2003} = 5^{(6 * 333 + 5)} (mod 7) \\[3ex] = (5^{6 * 333} * 5^5) \mod 7 ...Law\:\:1...Exp \\[3ex] = [(5^6)^{333} * 3125] \mod 7 \\[3ex] = (5^6)^{333} \mod 7 * 3125 \mod 7 \\[3ex] (5^6)^{333} \mod 7 = 1^{333} \mod 7 = 1 \mod 7 = 1 \\[3ex] 3125 \mod 7 = 3 \\[3ex] = 1 * 3 \\[3ex] = 3 \\[3ex] $ $\therefore 5^{2003} \mod 7$ = $3$

Check Digits for ISBNs

One of the applications of Modular Arithmetic is in the calculation of check digits for $ISBNs$

ISBN means International Standard Book Number
The ISBN is a unique identifier for any published book.
It is important for the publication, marketing, tracking, and the library use of books among others.
It is highly recommended that any published book be assigned an ISBN
It is highly recommended that the author of any published book (including self-publishing authors) purchase an ISBN for their books.
Published books include printed books, eBooks, and audio books among others.
Different editions of the same book should be assigned different ISBNs.
An eBook of the same printed book should have a different ISBN.
Prior to $2007$, an $ISBN$ has $10$ digits.
This was known as $1SBN-10$
The check digit is the $10-th$ digit.
From $2007$, an $ISBN$ has $13$ digits.
This is known as $ISBN-13$
The check digit is the $13-th$ digit

The Check Digit of an International Standard Book Number (ISBN) is the last digit of that number.

$\underline{For\:\:ISBN-10}$
$ISBN-10$ is developed in Modulo $11$
$0 - 10$ are the only numbers allowed in Modulo $11$
However, only ten digits are allowed.

Student: So, only ten digits are allowed?
Teacher: Yes, that is the reason for $ISBN-10$
Student: And the digits could be from $0$ through $10$?
Teacher: Yes, that is correct.
Do you know why?
Student: Because the system is in Modulo $11$.
Teacher: Correct...
Student: What if one or more of the digits was $10$?
Teacher: Very good question.
So, the $ISBN-10$ has $10$ digits
The first $9$ digits could be numbers from $0 - 9$
But, the last digit, the $10-th$ digit, which is also the check digit could be any number from $0 - 10$
When the check digit is $10$, it is written as $X$

The first $9$ digits could be numbers from $0 - 9$
The last digit is the $10-th$ digit, and it is also the check digit.
It could be any number from $0 - 10$
When the check digit is $10$, it is written as $X$

$\underline{For\:\:ISBN-13}$
$ISBN-13$ is developed in Modulo $10$
It has $13$ digits.
$0 - 9$ are the only numbers allowed in Modulo $10$
The check digit is the last digit, the $13-th$ digit.

What are the Uses of Check Digits?

Check Digit is used to:

(1.) Determine whether an $ISBN$ is valid or invalid.
If the calculation of the $ISBN$ leaves a remainder of $0$, then the $ISBN$ is valid.
If the calculation of the $ISBN$ does not have a remainder of $0$, then the $ISBN$ is invalid.

(2.) Verify if an $ISBN$ was recorded/entered correctly.

If a user enters the all the digits but the check digit of an $ISBN$ into an appropriate system (a system designed for ISBNs); the system calculates the check digit and compares it with the check digit entered by the user.
If the digits match, the $ISBN$ was entered correctly.
If the digits do not match, the $ISBN$ was not entered correctly.

(3.) Convert an $ISBN$ from $ISBN-10$ to $ISBN-13$

(4.) Convert an $ISBN$ from $ISBN-13$ to $ISBN-10$

Examples
For our examples, we shall use these $ISBNs$
We shall solve and verify.

Please review the Calculators for the examples.