Solved Examples on Modular Exponentiation

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

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$

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

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$

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

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

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

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$

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$

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$