Processing math: 0%

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)
It is the most powerful prayer. A pure heart, a clean mind, and a clear conscience is necessary for it.
- Samuel Dominic Chukwuemeka

"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

Solved Examples on Modular Exponentiation

Samuel Dominic Chukwuemeka (SamDom For Peace) 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.

(1.) Calculate 3^{57} \mod 317
Method: Fast Modular Multiplication

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

(2.)


This means that 231 needs to be converted to a number in base two.

\begin{array}{c|c} 2 & 231 \\ \hline 2 & 115 \:R\: 1 \\ \hline 2 & 57 \:R\: 1 \\ \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 \\[3ex] 231 = 11100111_2 \\[3ex] 231 = 11100111_2
(3.) Calculate 3^{57} \mod 317
Method: Modular Exponentiation Algorithm

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
(4.)


This means that 100632 needs to be converted to a number in base two.

\begin{array}{c|c} 2 & 100632 \\ \hline 2 & 50316 \:R\: 0 \\ \hline 2 & 25158 \:R\: 0 \\ \hline 2 & 12579 \:R\: 0 \\ \hline 2 & 6289 \:R\: 1 \\ \hline 2 & 3144 \:R\: 1 \\ \hline 2 & 1572 \:R\: 0 \\ \hline 2 & 786 \:R\: 0 \\ \hline 2 & 393 \:R\: 0 \\ \hline 2 & 196 \:R\: 1 \\ \hline 2 & 98 \:R\: 0 \\ \hline 2 & 49 \:R\: 0 \\ \hline 2 & 24 \:R\: 1 \\ \hline 2 & 12 \:R\: 0 \\ \hline 2 & 6 \:R\: 0 \\ \hline 2 & 3 \:R\: 0 \\ \hline 2 & 1 \:R\: 1 \\ \hline & 0 \:R\: 1 \end{array} Count \:the\: remainders\: upwards \\[3ex] 100632 = 11000100100011000_2 \\[3ex] 100632 = 11000100100011000_2
(5.) Calculate 11^{644} \mod 645
Method: Fast Modular Multiplication

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

(6.)


This means that 1001001101001010 in base two needs to be converted to a number in base sixteen.

We shall use the \:BIN \rightarrow DEC \rightarrow HEX \rightarrow OCT \rightarrow QUA \: Conversion Table

Each digit in HEX is equivalent to four digits in BIN
We split the digits in a set of four digits each.
1001001101001010_2
1001 \:0011\: 0100\: 1010
We have a complete set of four digits each. We are good.
We begin from behind
1010 = A
0100 = 4
0011 = 3
1001 = 9
We write it upwards (beginning from the bottom)
9 \:3\: 4\: A
\therefore 1001001101001010_2 = 934A_{16}
(7.) Calculate 11^{644} \mod 645
Method: Modular Exponentiation Algorithm

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
(8.)


This means that 934A in base sixteen needs to be converted to a number in base two.

We shall use the \:BIN \rightarrow DEC \rightarrow HEX \rightarrow OCT \rightarrow QUA \: Conversion Table

Each digit in HEX is equivalent to four digits in BIN
934A_{16}
We begin from behind
A = 1010
4 = 0100
3 = 0011
9 = 1001
We write it upwards (beginning from the bottom)
1001 \:0011\: 0100\: 1010
Remove any leading zero(s) if any.
Leading zeros are zeros that may be in front of the first set of digits.
In this case, there are no leading zeros.

\therefore 934A_{16} = 1001001101001010_2
(9.)


This means that CAF57 in base sixteen needs to be converted to a number in base two.

First Method:\:HEX \rightarrow DEC \rightarrow BIN
This is a long method.

HEX \rightarrow DEC \\[3ex] CAF57_{16} \\[3ex] = 12 * 16^4 + 10 * 16^3 + 15 * 16^2 + 5 * 16^1 + 7 * 16^0 \\[3ex] = 12 * 65536 + 10 * 4096 + 15 * 256 + 5 * 16 + 7 * 1 \\[3ex] = 786432 + 40960 + 3840 + 80 + 7 \\[3ex] \therefore CAF57_{16} = 831319 \\[3ex] DEC \rightarrow BIN \\[3ex] \begin{array}{c|c} 2 & 831319 \\ \hline 2 & 415659 \:R\: 1 \\ \hline 2 & 207829 \:R\: 1 \\ \hline 2 & 103914 \:R\: 1 \\ \hline 2 & 51957 \:R\: 0 \\ \hline 2 & 25978 \:R\: 1 \\ \hline 2 & 12989 \:R\: 0 \\ \hline 2 & 6494 \:R\: 1 \\ \hline 2 & 3247 \:R\: 0 \\ \hline 2 & 1623 \:R\: 1 \\ \hline 2 & 811 \:R\: 1 \\ \hline 2 & 405 \:R\: 1 \\ \hline 2 & 202 \:R\: 1 \\ \hline 2 & 101 \:R\: 0 \\ \hline 2 & 50 \:R\: 1 \\ \hline 2 & 25 \:R\: 0 \\ \hline 2 & 12 \:R\: 1 \\ \hline 2 & 6 \:R\: 0 \\ \hline 2 & 3 \:R\: 0 \\ \hline 2 & 1 \:R\: 1 \\ \hline & 0 \:R\: 1 \end{array} Count \:the\: remainders\: upwards \\[3ex] 831319 = 11001010111101010111_2 \\[3ex] CAF57_{16} = 11001010111101010111_2

Second Method:\:BIN \rightarrow DEC \rightarrow HEX \rightarrow OCT \rightarrow QUA \: Conversion Table
This is a short method.

Remember that each digit in HEX is equivalent to four digits in BIN
CAF57_{16}
We begin from behind
7 = 0111
5 = 0101
F = 1111
A = 1010
C = 1100
We write it upwards (beginning from the bottom)
1100 \:1010\: 1111\: 0101\: 0111
Remove any leading zero(s) if any.
Leading zeros are zeros that may be in front of the first set of digits.
In this case, there are no leading zeros.

\therefore CAF57_{16} = 11001010111101010111_2
(10.)


This means that 75C in base sixteen needs to be converted to a number in base two.

First Method:\:HEX \rightarrow DEC \rightarrow BIN
This is a long method.

HEX \rightarrow DEC \\[3ex] 75C_{16} \\[3ex] = 7 * 16^2 + 5 * 16^1 + 12 * 16^0 \\[3ex] = 7 * 256 + 5 * 16 + 12 * 1 \\[3ex] = 1792 + 80 + 12 \\[3ex] \therefore 75C_{16} = 1884 \\[3ex] DEC \rightarrow BIN \\[3ex] \begin{array}{c|c} 2 & 1884 \\ \hline 2 & 942 \:R\: 0 \\ \hline 2 & 471 \:R\: 0 \\ \hline 2 & 235 \:R\: 1 \\ \hline 2 & 117 \:R\: 1 \\ \hline 2 & 58 \:R\: 1 \\ \hline 2 & 29 \:R\: 0 \\ \hline 2 & 14 \:R\: 1 \\ \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 \\[3ex] 1884 = 11101011100_2 \\[3ex] 75C_{16} = 11101011100_2

Second Method:\:BIN \rightarrow DEC \rightarrow HEX \rightarrow OCT \rightarrow QUA \: Conversion Table
This is a short method.

Remember that each digit in HEX is equivalent to four digits in BIN
75C_{16}
We begin from behind
C = 1100
5 = 0101
7 = 0111
We write it upwards (beginning from the bottom)
0111 \:0101\: 1100
Remove any leading zero(s) if any.
Leading zeros are zeros that may be in front of the first set of digits.
In this case, there is only one leading zero.
111 \:0101\: 1100

\therefore 75C_{16} = 11101011100_2