For in GOD we live, and move, and have our being.
 Acts 17:28
The Joy of a Teacher is the Success of his Students.
 Samuel Dominic Chukwuemeka
I greet you this day,
First: Review the Notes. Second: View the Videos. Third: Solve the questions. Fourth: Check your solutions with my thoroughlyexplained solutions. Fifth: Check your answers with the calculators.
I wrote the codes for some of these calculators using JavaScript, a clientside scripting language. Please use the latest Internet browsers. I used the AJAX Javascript library for the rest of the codes.
Comments, ideas, areas of improvement, questions, and constructive criticisms are welcome. Should you need to contact me, please use the form at the bottom of the page. Thank you for visiting!!!
Samuel Dominic Chukwuemeka (Samdom For Peace) B.Eng., A.A.T, M.Ed., M.S
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.



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 $32bit$ or $64bit$ computer?
Imagine writing a 32bit (a 32binary 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$  $0000$  $0001$  $0010$  $0011$  $0100$  $0101$  $0110$  $0111$  $1000$  $1001$  $1010$  $1011$  $1100$  $1101$  $1110$  $1111$ 
$DEC$  $0$  $1$  $2$  $3$  $4$  $5$  $6$  $7$  $8$  $9$  $10$  $11$  $12$  $13$  $14$  $15$ 
$HEX$  $0$  $1$  $2$  $3$  $4$  $5$  $6$  $7$  $8$  $9$  $A$  $B$  $C$  $D$  $E$  $F$ 
$OCT$  $0$  $1$  $2$  $3$  $4$  $5$  $6$  $7$  $10$  $11$  $12$  $13$  $14$  $15$  $16$  $17$ 
$QUA$  $0$  $1$  $2$  $3$  $10$  $11$  $12$  $13$  $20$  $21$  $22$  $23$  $30$  $31$  $32$  $33$ 
We can add, subtract, multiply, and divide nonnegative 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$
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 $12hour$ 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 $24hour$ format? How does it work? What number does it begin? What number does it end?
$3:00\: pm$ in a $12hour$ format is equivalent to what time in a $24hour$ format?
What are some organizations that use the $12hour$ format? $24hour$ 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$ $(24hour)$ format, or $4:00\: pm$ $12hour)$ format
This means that $16 \mod 12 = 4$ (12hour) format) OR
This means that $16 \mod 24 = 16$ (24hour 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 $$
$$ 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 $$
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 \\[5ex]
12 \mod 9 \\[3ex]
9 = 0 \\[3ex]
10 = 1 \\[3ex]
11 = 2 \\[3ex]
12 = 3 \\[3ex]
\therefore 12 \mod 9 = 3
$$
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?
$$ \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 $$
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?
$5  9 = 1 \:R\: 4$ (negative quotient is okay, negative remainder is not okay)
Check: $9 = (5 * 1) + (4) $
$
quotient = 1 \\[3ex]
Subtract\:\:1\:\:from\:\:the\:\:quotient \\[3ex]
1  1 = 2 \\[3ex]
5 * 2 = 10 \\[3ex]
10 + x = 9 \\[3ex]
x = 9 + 10 = 1 \\[3ex]
$
$5  9 = 2 \:R\: 1$ (negative quotient is okay, positive remainder is okay)
Check: $9 = (5 * 2) + 1 $
$\therefore 9 \mod 5 = 1$
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 \\[3ex]
$
$+$  $0$  $1$  $2$  $3$  $4$ 

$0$  $0$  $1$  $2$  $3$  $4$ 
$1$  $1$  $2$  $3$  $4$  $0$ 
$2$  $2$  $3$  $4$  $0$  $1$ 
$3$  $3$  $4$  $0$  $1$  $2$ 
$4$  $4$  $0$  $1$  $2$  $3$ 
$*$  $0$  $1$  $2$  $3$  $4$ 

$0$  $0$  $0$  $0$  $0$  $0$ 
$1$  $0$  $1$  $2$  $3$  $4$ 
$2$  $0$  $2$  $4$  $1$  $3$ 
$3$  $0$  $3$  $1$  $4$  $2$ 
$4$  $0$  $4$  $3$  $2$  $1$ 



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 lifelong 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}{cc c}
2 & 12 & 18 \\
\hline
3 & 6 & 9 \\
\hline
& 2 & 3
\end{array}
$$
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}{cc c}
3 & 30 & 105 \\
\hline
5 & 10 & 35 \\
\hline
& 2 & 7
\end{array}
$$
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$



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.
$\boldsymbol{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
$
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
This method is great!
You 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$
$a = 9$
$b = 4$
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$
$r = a  bq$
$r = a  qb$
But, $c = a$ and $d = b$
$c = dq + r$
$r = c  dq$
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$
$9 = 4 * 2 + 1$
$9 = 2 * 4 + 1$
$1 = 9  2 * 4$
We then have to express it in terms of $a$ and $b$
Remember (Original): $a = 9$; $b = 4$
$1 = a  2b$ ...eqn(1)
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)$
From $1 = 9  2 * 4$
$r = c  qd$
$r = 1$
$c = 9$
$d = 4$
$q = 2$
Replace $c$ and $d$ with $d$ and $r$ respectively
$c = 4$
$d = 1$
Go back to Step 2
$c = dq + r$
For $(c, d) = (4, 1)$
4 = 1 * 4 + 0
$r = 0$
Stop.
Express $r$ in terms of $a$ and $b$
$r = c  qd$
$0 = 4  4 * 1$
Remember (Original): $a = 9$; $b = 4$
From Equation (1.);
$1 = a  2b$ ...eqn(1)
Subst. $a  2b$ for $1$
$0 = 4  4(a  2b)$
$0 = 4  4a + 8b$
$0 = b  4a + 8b$
$0 = 4a + 9b$
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$
$1 = 9  2 * 4$
Remember: $gcd(a, b) = ma + nb$
$1 = 1 * 9  2 * 4$
$1 = 1 * 9 + 2 * 4$
$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.
Steps  $c$  $d$  $q$  $r$  Conclusion 
Step 1  $9$  $4$  
Step 2  $9$  $4$  $2$  $1$ 
$1 = 9  2 * 4$ $1 = a  2b$ 
Step 3  $4$  $1$  $4$  $0$ 
$0 = 4  4 * 1$ $0 = 4  4(a  2b)$ $0 = 4  4a + 8b$ $0 = b  4a + 8b$ $0 = 4a + 9b$ 
Step 4 
$gcd(a, b) = 1$ $1 = a  2b$ $1 = 9  2 * 4$ $1 = 1 * 9  2 * 4$ $1 = 1 * 9 + 2 * 4$ $m = 1; n = 2$ Inverse of $4 \mod 9$ $= 2 \mod 9$ $= 7 \mod 9$ $= 7$ 
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}$
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
$
$\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
$
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
$
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 "backsubstitute" till the final congrunce and the final equation.
This is for Relatively Prime Moduli only where:
(1.) each modulo is a positive integer greater than $1$
(2.) the coefficient of the variable is $1$
If the coefficient of the variable is not equal to $1$, divide both sides (do not include the modulo)
by the coefficient of the variable. This works for relatively prime moduli.



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$
$1^{st}$ Step: Convert the exponent to a binary base.
$$
\begin{array}{cc}
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
$$
$2^{nd}$ 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}
$$
$3^{rd}$ 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$
$1^{st}$ Step: Convert the exponent to a binary base.
$$
\begin{array}{cc}
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
$$
$2^{nd}$ 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}
$$
$3^{rd}$ 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$
$1^{st}$ 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]
$
$2^{nd}$ Step: Find the binary representation of $b$
$$
\begin{array}{cc}
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$
$3^{rd}$ 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 stepbystep
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.
$i$  $8$  $7$  $6$  $5$  $4$  $3$  $2$  $1$  $0$ 
$b_i$  $1$  $0$  $0$  $1$  $0$  $1$  $1$  $1$  $0$ 
$c$  $1$  $2$  $4$  $9$  $18$  $37$  $75$  $151$  $302$ 
$d$  $3$  $4$  $1$  $3$  $4$  $3$  $2$  $2$  $4$ 
return $d$
$\therefore 3^{302} \mod 5$ = $4$
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}{cc}
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 stepbystep
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$
$i$  $10$  $9$  $8$  $7$  $6$  $5$  $4$  $3$  $2$  $1$  $0$ 
$b_i$  $1$  $1$  $1$  $1$  $1$  $0$  $1$  $0$  $0$  $1$  $1$ 
$c$  $1$  $3$  $7$  $15$  $31$  $62$  $125$  $250$  $500$  $1001$  $2003$ 
$d$  $5$  $6$  $5$  $6$  $5$  $4$  $3$  $2$  $4$  $3$  $3$ 
return $d$
$\therefore 5^{2003} \mod 7$ = $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
$
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$



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 selfpublishing 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 $1SBN10$
The check digit is the $10th$ digit.
From $2007$, an $ISBN$ has $13$ digits.
This is known as $ISBN13$
The check digit is the $13th$ digit
The Check Digit of an International Standard Book Number (ISBN) is the last digit
of that number.
$\underline{For\:\:ISBN10}$
$ISBN10$ 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 $ISBN10$
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 $ISBN10$ has $10$ digits
The first $9$ digits could be numbers from $0  9$
But, the last digit, the $10th$ 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 $10th$ 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\:\:ISBN13}$
$ISBN13$ 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 $13th$ digit.
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 $ISBN10$ to $ISBN13$
(4.) Convert an $ISBN$ from $ISBN13$ to $ISBN10$
Examples
For our examples, we shall use these $ISBNs$
We shall solve and verify.
$\boldsymbol{Example\:1}$ Calculate the check digit of the $ISBN10: $
These calculators will not allow you to:
(1.) Type a negative number.
(2.) Type more than a single digit in each text box.
(3.) Delete place holders.
Given: The $9$ Digits of a $10Digit$ ISBN
To Find: The Check Digit
Given: A $10Digit$ ISBN
To Determine: If it is valid or invalid
To Convert: To a $13Digit$ ISBN
NOTE: If the check digit is an "X", please type the uppercase X (not lowercase x) as is.
Given: The $12$ Digits of a $13Digit$ ISBN
To Find: The Check Digit
Given: A $13Digit$ ISBN
To Determine: If it is valid or invalid
To Convert: To a $10Digit$ ISBN
Chukwuemeka, S.D (2016, April 30). Samuel Chukwuemeka Tutorials  Math, Science, and Technology.
Retrieved from https://www.samuelchukwuemeka.com
Rosen, K. H. (2013). Discrete mathematics and its applications ($8^{th}$ ed.).
New York: McGrawHill.
Tan, S. (2015). Finite Mathematics for the Managerial, Life, and Social Sciences (Revised/Expanded ed.).
Boston: Cengage Learning.
CrackACT  Free ACT Past Questions. (n.d.). Retrieved from http://www.crackact.com/actdownloads/
CAREER INDIA  Free CMAT Past Questions. (n.d). Retrieved from https://www.careerindia.com/entranceexam/cmatquestionpaperse23.html
CSEC Math Tutor  Free Caribbean Secondary Education Certificate Examination (CSEC) Past Questions. (n.d). Retrieved from https://www.csecmathtutor.com/pastpapers.html
MySchoolGist  Free West African Senior School Certificate Examination (WASSCE) Past Questions. (n.d). Retrieved from https://www.myschoolgist.com/ng/freewaecpastquestionsandanswers/
ISBN Information. (n.d). Retrieved from https://isbninformation.com/checkdigitforthe13digitisbn.html
VAST LEARNERS  Free JAMB Past Questions. (n.d). Retrieved from https://www.vastlearners.com/freejambpastquestions/