If there is one prayer that you should pray/sing every day and every hour, it is the
LORD's prayer (Our FATHER in Heaven prayer)
- Samuel Dominic Chukwuemeka
It is the most powerful prayer.
A pure heart, a clean mind, and a clear conscience is necessary for it.
"Ananias, Azarias, Misael, bless the LORD; Praise and exalt Him above all forever." - Canticle of the Three Youths
The Joy of a Teacher is the Success of his Students.
- Samuel Dominic Chukwuemeka
Verify your answers as applicable with the
Modulo Arithmetic and Algorithms Calculators
Solve all questions.
Use the four methods for each question where applicable.
Name each method that you use.
If any method is not applicable, state the reason(s) why it is not applicable.
Verify that you have the same answer for each question using the methods.
Show all work.
1st Step: Convert the exponent to a binary base.
\begin{array}{c|c}
2 & 57 \\
\hline
2 & 28 \:R\: 1 \\
\hline
2 & 14 \:R\: 0 \\
\hline
2 & 7 \:R\: 0 \\
\hline
2 & 3 \:R\: 1 \\
\hline
2 & 1 \:R\: 1 \\
\hline
& 0 \:R\: 1
\end{array}
Count \:the\: remainders\: upwards
57 = 111001_2
2nd Step: Write the place values of the binary digit.
\begin{align}
2^5\ \ 2^4\ \ 2^3\ \ 2^2\ \ 2^1\ \ 2^0\ \ \\
1\ \ \ 1\ \ \ 1\ \ \ 0\ \ \ 0\ \ \ 1~~\ \ \
\end{align}
3rd Step: Simplify. Write the main problem as a product of smaller exponents.
3^{57} = 3^{(1 * 2^5 + 1 * 2^4 + 1 * 2^3 + 0 * 2^2 + 0 * 2^1 + 1 * 2^0)} \\[3ex]
= 3^{(1 * 32 + 1 * 16 + 1 * 8 + 0 * 4 + 0 * 2 + 1 * 1)} \\[3ex]
= 3^{(32 + 16 + 8 + 0 + 0 + 1)} \\[3ex]
Apply \:the\: laws\: of\: exponents \\[3ex]
= 3^{32} * 3^{16} * 3^8 * 3^0 * 3^0 * 3^1 \\[3ex]
= 3^{32} * 3^{16} * 3^8 * 1 * 1 * 1 * 3 \\[3ex]
Going\: forward\:, we\: shall\: forget\: the\: zeros \\[3ex]
There\: is\: no\: need\: to\: write\: them \\[3ex]
Because\: any\: base\: exponent\: zero\: gives\: 1 \\[3ex]
3^{57} \mod 317 \\[3ex]
= (3^{32} * 3^{16} * 3^8 * 3) \mod 317 \\[3ex]
= 3^{32} \mod 317 * 3^{16} \mod 317 * 3^8 \mod 317 * 3 \mod 317 \\[3ex]
3 \mod 317 = \color{red}{3} \\[3ex]
We\: have\: 3^8, \:3^{16}, \:3^{32} \\[3ex]
My\: advice:\: Do\: it\: in\: twos\: assume\: 3^8\: gave\: a\: large\: result \\[3ex]
However,\: 3^8 = 6561 \\[3ex]
So,\: we\: can\: go\: ahead\: and\: do\: it\: directly \\[3ex]
3^8 \mod 317 \\[3ex]
= 6561 \mod 317 \\[3ex]
= \color{red}{221} \\[3ex]
3^{16} \mod 317 = (3^8)^2 \mod 317 \\[3ex]
= (221)^2 \mod 317 \\[3ex]
= 48841 \mod 317 = \color{red}{23} \\[3ex]
3^{32} \mod 317 = (3^{16})^2 \mod 317 \\[3ex]
= (23)^2 \mod 317 \\[3ex]
= 529 \mod 317 \\[3ex]
= \color{red}{212} \\[3ex]
3^{57} \mod 317 \\[3ex]
= (3^{32} * 3^{16} * 3^8 * 3) \mod 317 \\[3ex]
= (3^{32} \mod 317 * 3^{16} \mod 317 * 3^8 \mod 317 * 3 \mod 317) \mod 317 \\[3ex]
= (212 * 23 * 221 * 3) \mod 317 \\[3ex]
= 3232788 \mod 317 \\[3ex]
= 22 \\[3ex]
\therefore 3^{57} \mod 317 = 22
1st Step: Write the values of a, b, n
Compare 3^{57} \mod 317 to a^b \mod n
a = 3 \\[3ex]
b = 57 \\[3ex]
n = 317 \\[3ex]
2nd Step: Find the binary representation of b
\begin{array}{c|c}
2 & 57 \\
\hline
2 & 28 \:R\: 1 \\
\hline
2 & 14 \:R\: 0 \\
\hline
2 & 7 \:R\: 0 \\
\hline
2 & 3 \:R\: 1 \\
\hline
2 & 1 \:R\: 1 \\
\hline
& 0 \:R\: 1
\end{array}
Count \:the\: remainders\: upwards
57 = \langle 111001 \rangle
3rd Step: Form a table and use the Modular Exponentiation algorithm to solve the problem.
57 = \langle 111001 \rangle \\[3ex]
\langle 111001 \rangle = 111001_2 \\[3ex]
= 1 * 2^5 + 1 * 2^4 + 1 * 2^3 + 0 * 2^2 + 0 * 2^1 + 1 * 2^0 \\[3ex]
This means that: i = 5...down\: to\: 0
i are the exponents.
b_i are the binary representations (the face values).
a = 3 \\[3ex]
b = 57 \\[3ex]
n = 317 \\[3ex]
b_5 = 1 \\[3ex]
b_4 = 1 \\[3ex]
b_3 = 1 \\[3ex]
b_2 = 0 \\[3ex]
b_1 = 0 \\[3ex]
b_0 = 1 \\[3ex]
Let us do the algorithm step-by-step
Initial: c = 0, d = 1
For i = 5
b_5 = 1
c = 2c
c = 2 * 0
c = 0
d = (d * d) \mod n
d = (1 * 1) \mod 317
d = 1 \mod 317
d = 1
But b_5 = 1
c = c + 1
c = 0 + 1
c = 1
d = (d * a) \mod n
d = (1 * 3) \mod 317
d = 3 \mod 317
d = 3
We shall not initial again. The initialization is for the first case.
For i = 4
b_4 = 1
c = 2c
c = 2 * 1
c = 2
d = (d * d) \mod n
d = (3 * 3) \mod 317
d = 9 \mod 317
d = 9
But b_4 = 1
c = c + 1
c = 2 + 1
c = 3
d = (d * a) \mod n
d = (9 * 3) \mod 317
d = 27 \mod 317
d = 27
For i = 3
b_3 = 1
c = 2c
c = 2 * 3
c = 6
d = (d * d) \mod n
d = (27 * 27) \mod 317
d = 729 \mod 317
d = 95
But b_3 = 1
c = c + 1
c = 6 + 1
c = 7
d = (d * a) \mod n
d = (95 * 3) \mod 317
d = 285 \mod 317
d = 285
For i = 2
b_2 = 0
c = 2c
c = 2 * 7
c = 14
d = (d * d) \mod n
d = (285 * 285) \mod 317
d = 81225 \mod 317
d = 73
But b_2 = 0
Stop.
For i = 1
b_1 = 0
c = 2c
c = 2 * 14
c = 28
d = (d * d) \mod n
d = (73 * 73) \mod 317
d = 5329 \mod 317
d = 257
But b_1 = 0
Stop.
For i = 0
b_0 = 1
c = 2c
c = 2 * 28
c = 56
d = (d * d) \mod n
d = (257 * 257) \mod 317
d = 66049 \mod 317
d = 113
But b_0 = 1
c = c + 1
c = 56 + 1
c = 57
d = (d * a) \mod n
d = (113 * 3) \mod 317
d = 339 \mod 317
d = 22
i | 5 | 4 | 3 | 2 | 1 | 0 |
b_i | 1 | 1 | 1 | 0 | 0 | 1 |
c | 1 | 3 | 7 | 14 | 28 | 57 |
d | 3 | 27 | 285 | 73 | 257 |
22 return d |
\therefore 3^{57} \mod 317 = 22 |
1st Step: Convert the exponent to a binary base.
\begin{array}{c|c}
2 & 644 \\
\hline
2 & 322 \:R\: 0 \\
\hline
2 & 161 \:R\: 0 \\
\hline
2 & 80 \:R\: 1 \\
\hline
2 & 40 \:R\: 0 \\
\hline
2 & 20 \:R\: 1 \\
\hline
2 & 10 \:R\: 0 \\
\hline
2 & 5 \:R\: 1 \\
\hline
2 & 2 \:R\: 1 \\
\hline
2 & 1 \:R\: 0 \\
\hline
& 0 \:R\: 1
\end{array}
Count \:the\: remainders\: upwards
644 = 1010000100_2
2nd Step: Write the place values of the binary digit.
\begin{align}
2^9\ \ 2^8\ \ 2^7\ \ 2^6\ \ 2^5\ \ 2^4\ \ 2^3\ \ 2^2\ \ 2^1\ \ 2^0 \\
1\ \ \ 0\ \ \ 1\ \ \ 0\ \ \ \ 0\ \ \ \ 0\ \ \ \ 0\ \ \ \ 1\ \ \ 0\ \ \ 0\ \ \
\end{align}
3rd Step: Simplify. Write the main problem as a product of smaller exponents.
11^{644} \\[3ex]
Forget\: the\: zeros \\[3ex]
= 11^{(1 * 2^9 + 1 * 2^7 + 1 * 2^2)} \\[3ex]
= 11^{(1 * 512 + 1 * 128 + 1 * 4)} \\[3ex]
= 11^{(512 + 128 + 4)} \\[3ex]
Apply \:the\: laws\: of\: exponents \\[3ex]
= 11^{512} * 11^{128} * 11^4 \\[3ex]
11^{644} \mod 645 \\[3ex]
= (11^{512} * 11^{128} * 11^4) \mod 645 \\[3ex]
= 11^{512} \mod 645 * 11^{128} \mod 645 * 11^4 \mod 645 \\[3ex]
11^4 \mod 645 \\[3ex]
= 14641 \mod 645 \\[3ex]
= \color{red}{451} \\[3ex]
We\: have\: 11^4, 11^{128}, 11^{512} \\[3ex]
My\: advice:\: Do\: it\: gradually\: because\: 11^{128} \:gives\: a\: large\: result \\[3ex]
Let\: us\: do\: 11^8, 11^{16}, 11^{32}, ... \\[3ex]
We \:may\: skip\: around\: if\: we\: find\: a\: result\: that\: is\: not\: large \\[3ex]
11^8 \mod 645 \\[3ex]
= (11^4)^2 \mod 645 \\[3ex]
= 451^2 \mod 645 \\[3ex]
= 203401 \mod 645 \\[3ex]
= 226 \\[3ex]
11^{16} \mod 645 \\[3ex]
= (11^8)^2 \mod 645 \\[3ex]
= 226^2 \mod 645 \\[3ex]
= 51076 \mod 645 \\[3ex]
= 121 \\[3ex]
11^{32} \mod 645 \\[3ex]
= (11^{16})^2 \mod 645 \\[3ex]
= 121^2 \mod 645 \\[3ex]
= 14641 \mod 645 \\[3ex]
= 451 \\[3ex]
Did\: you\: notice\: something?\: \\[3ex]
Let\: us\: save\: some\: time \\[3ex]
11^{64} \mod 645 \\[3ex]
= (11^{32})^2 \mod 645 \\[3ex]
= 451^2 \mod 645 \\[3ex]
= 226 \\[3ex]
11^{128} \mod 645 \\[3ex]
= (11^{64})^2 \mod 645 \\[3ex]
= \color{red}{121} \\[3ex]
11^{256} \mod 645 \\[3ex]
= (11^{128})^2 \mod 645 \\[3ex]
= 451 \\[3ex]
11^{512} \mod 645 \\[3ex]
= (11^{256})^2 \mod 645 \\[3ex]
= \color{red}{226} \\[3ex]
11^{644} \mod 645 \\[3ex]
= (11^{512} * 11^{128} * 11^4) \mod 645 \\[3ex]
= (11^{512} \mod 645 * 11^{128} \mod 645 * 11^4 \mod 645) \mod 645 \\[3ex]
= (226 * 121 * 451) \mod 645 \\[3ex]
= 12333046 \mod 645 \\[3ex]
= 1 \\[3ex]
\therefore 11^{644} \mod 645 = 1
1st Step: Write the values of a, b, n
Compare 11^{644} \mod 645 to a^b \mod n
a = 11 \\[3ex]
b = 644 \\[3ex]
n = 645 \\[3ex]
2nd Step: Find the binary representation of b
\begin{array}{c|c}
2 & 644 \\
\hline
2 & 322 \:R\: 0 \\
\hline
2 & 161 \:R\: 0 \\
\hline
2 & 80 \:R\: 1 \\
\hline
2 & 40 \:R\: 0 \\
\hline
2 & 20 \:R\: 0 \\
\hline
2 & 10 \:R\: 0 \\
\hline
2 & 5 \:R\: 0 \\
\hline
2 & 2 \:R\: 1 \\
\hline
2 & 1 \:R\: 0 \\
\hline
& 0 \:R\: 1
\end{array}
Count \:the\: remainders\: upwards
644 = \langle 1010000100 \rangle
3^{rd} Step: Form a table and use the Modular Exponentiation algorithm to solve the problem.
644 = \langle 1010000100 \rangle \\[3ex]
\langle 1010000100 \rangle = 1010000100_2 \\[3ex]
= 1 * 2^9 + 0 * 2^8 + 1 * 2^7 + 0 * 2^6 + 0 * 2^5 + 0 * 2^4 + 0 * 2^3 + 1 * 2^2 + 0 * 2^1 + 0 * 2^0 \\[3ex]
This means that: i = 9...down\: to\: 0
i are the exponents.
b_i are the binary representations (the face values).
a = 11 \\[3ex]
b = 644 \\[3ex]
n = 645 \\[3ex]
b_9 = 1 \\[3ex]
b_8 = 0 \\[3ex]
b_7 = 1 \\[3ex]
b_6 = 0 \\[3ex]
b_5 = 0 \\[3ex]
b_4 = 0 \\[3ex]
b_3 = 0 \\[3ex]
b_2 = 1 \\[3ex]
b_1 = 0 \\[3ex]
b_0 = 0 \\[3ex]
Let us do the algorithm step-by-step
Initial: c = 0, d = 1
For i = 9
b_9 = 1
c = 2c
c = 2 * 0
c = 0
d = (d * d) \mod n
d = (1 * 1) \mod 645
d = 1 \mod 645
d = 1
But b_9 = 1
c = c + 1
c = 0 + 1
c = 1
d = (d * a) \mod n
d = (1 * 11) \mod 645
d = 11 \mod 645
d = 11
We shall not initial again. The initialization is for the first case.
For i = 8
b_8 = 0
c = 2c
c = 2 * 1
c = 2
d = (d * d) \mod n
d = (11 * 11) \mod 645
d = 121 \mod 645
d = 121
But b_8 = 0
Stop.
For i = 7
b_7 = 1
c = 2c
c = 2 * 2
c = 4
d = (d * d) \mod n
d = (121 * 121) \mod 645
d = 14641 \mod 645
d = 451
But b_7 = 1
c = c + 1
c = 4 + 1
c = 5
d = (d * a) \mod n
d = (451 * 11) \mod 645
d = 4961 \mod 645
d = 446
For i = 6
b_6 = 0
c = 2c
c = 2 * 5
c = 10
d = (d * d) \mod n
d = (446 * 446) \mod 645
d = 198916 \mod 645
d = 256
But b_6 = 0
Stop.
For i = 5
b_5 = 0
c = 2c
c = 2 * 10
c = 20
d = (d * d) \mod n
d = (256 * 256) \mod 645
d = 65536 \mod 645
d = 391
But b_5 = 0
Stop.
For i = 4
b_4 = 0
c = 2c
c = 2 * 20
c = 40
d = (d * d) \mod n
d = (391 * 391) \mod 645
d = 152881 \mod 645
d = 16
But b_4 = 0
Stop.
For i = 3
b_3 = 0
c = 2c
c = 2 * 40
c = 80
d = (d * d) \mod n
d = (16 * 16) \mod 645
d = 256 \mod 645
d = 256
But b_3 = 0
Stop.
For i = 2
b_2 = 1
c = 2c
c = 2 * 80
c = 160
d = (d * d) \mod n
d = (256 * 256) \mod 645
d = 65536 \mod 645
d = 391
But b_2 = 1
c = c + 1
c = 160 + 1
c = 161
d = (d * a) \mod n
d = (391 * 11) \mod 645
d = 4301 \mod 645
d = 431
For i = 1
b_1 = 0
c = 2c
c = 2 * 161
c = 322
d = (d * d) \mod n
d = (431 * 431) \mod 645
d = 185761 \mod 645
d = 1
But b_1 = 0
Stop.
For i = 0
b_0 = 0
c = 2c
c = 2 * 322
c = 644
d = (d * d) \mod n
d = (1 * 1) \mod 645
d = 1 \mod 645
d = 1
But b_0 = 0
Stop.
i | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
b_i | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
c | 1 | 2 | 5 | 10 | 20 | 40 | 80 | 161 | 322 | 644 |
d | 11 | 121 | 446 | 256 | 391 | 16 | 256 | 431 | 1 |
1 return d |
\therefore 11^{644} \mod 645 = 1 |