Modular Arithmetic and Algorithms

This means that $11000100100011000$ in base two needs to be converted to a number in base ten.

$ 11000100100011000_2 \\[3ex] = 1 * 2^{16} + 1 * 2^{15} + 0 * 2^{14} + 0 * 2^{13} + 0 * 2^{12} + 1 * 2^{11} + 0 * 2^{10} + 0 * 2^9 + 1 * 2^8 + 0 * 2^7 + 0 * 2^6 + 0 * 2^5 + 1 * 2^4 + 1 * 2^3 + 0 * 2^2 + 0 * 2^1 + 0 * 2^0 \\[3ex] = 1 * 65536 + 1 * 32768 + 0 * 16384 + 0 * 8192 + 0 * 4096 + 1 * 2048 + 0 * 1024 + 0 * 512 + 1 * 256 + 0 * 128 + 0 * 64 + 0 * 32 + 1 * 16 + 1 * 8 + 0 * 4 + 0 * 2 + 0 * 1 \\[3ex] = 65536 + 32768 + 0 + 0 + 0 + 2048 + 0 + 0 + 256 + 0 + 0 + 0 + 16 + 8 + 0 + 0 + 0 \\[3ex] = 100632 \\[3ex] $ ∴ $11100111_2 = 100632$

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} \text{Count the remainders upwards} \\[3ex] 100632 = 11000100100011000_2 \\[3ex] $ ∴ $100632 = 11000100100011000_2$

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

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

$ BIN \rightarrow DEC \\[3ex] 11101011100_2 \\[3ex] = 1 * 2^{10} + 1 * 2^9 + 1 * 2^8 + 0 * 2^7 + 1 * 2^6 + 0 * 2^5 + 1 * 2^4 + 1 * 2^3 + 1 * 2^2 + 0 * 2^1 + 0 * 2^0 \\[3ex] = 1 * 1024 + 1 * 512 + 1 * 256 + 0 * 128 + 1 * 64 + 0 * 32 + 1 * 16 + 1 * 8 + 1 * 4 + 0 * 2 + 0 * 1 \\[3ex] = 1024 + 512 + 256 + 0 + 64 + 0 + 16 + 8 + 4 + 0 + 0 \\[3ex] \therefore 11101011100_2 = 1884 \\[3ex] DEC \rightarrow HEX \\[3ex] \begin{array}{c|c} 16 & 1884 \\ \hline 16 & 117 \:R\: 12 \\ \hline 16 & 7 \:R\: 5 \\ \hline & 0 \:R\: 7 \end{array} \text{Count the remainders upwards} \\[3ex] 1884 = 7\: 5\: {12} \\[3ex] 12 = C_{16} \\[3ex] 1884 = 75C \\[3ex] $ ∴ $11101011100_2 = 75C_{16}$

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

Each digit in $HEX$ is equivalent to four digits in $BIN$
We split the digits in a set of four digits each.

$ 11101011100_2 111\: 0101\: 1100 \\[3ex] $ We have two complete sets of four digits each. But we have one incomplete set.
We will need to complete the first incomplete set by adding a $0$
$0111\: 0101\: 1100$
We begin from behind

$ 1100 = C \\[3ex] 0101 = 5 \\[3ex] 0111 = 7 \\[3ex] $ We write it upwards (beginning from the bottom)
$7 \:5\: C$

∴ $\therefore 11101011100_2 = 75C_{16}$

Third Method:$\:BIN \rightarrow HEX\:$ Method
This is also a short method.

Each digit in $HEX$ is equivalent to four digits in $BIN$
We split the digits in a set of four digits each.
$11101011100_2$
$111\: 0101\: 1100$
We have two complete sets of four digits each. But we have one incomplete set.
We will need to complete the first incomplete set by adding a $0$
$0111\: 0101\: 1100$
These are the face values.
Let us write the place values beneath the face values.
$ 0\ \ \ 1\ \ \ 1\ \ \ 1\ \ \ \ \ \ \ \ 0\ \ \ 1\ \ \ 0\ \ \ 1\ \ \ \ \ \ \ 1\ \ \ 1\ \ \ 0\ \ \ 0\ \ \ \ \\ 2^3\ 2^2\ 2^1\ 2^0\ \ \ \ \ \ 2^3\ 2^2\ 2^1\ 2^0\ \ \ \ \ \ \ 2^3\ 2^2\ 2^1\ 2^0\ \ \ \ $

$ 0\ 1\ 1\ 1\ \ \ \ \ 0\ 1\ 0\ 1\ \ \ \ \ 1\ 1\ 0\ 0\ \ \ \ \\ 8\ 4\ 2\ 1\ \ \ \ \ 8\ 4\ 2\ 1\ \ \ \ \ 8\ 4\ 2\ 1\ \ \ \ $

Draw a line beneath the place values (as you would do with addition, subtraction, division, etc.)

$ \begin{align} 0\ 1\ 1\ 1\ \ \ \ \ 0\ 1\ 0\ 1\ \ \ \ \ 1\ 1\ 0\ 0\ \ \ \ \\ 8\ 4\ 2\ 1\ \ \ \ \ 8\ 4\ 2\ 1\ \ \ \ \ 8\ 4\ 2\ 1\ \ \ \ \\ \hline \end{align} $

For each face value of $0$, write a $0$ under the corresponding place value
For each face value that is not a $0$, write the value of the corresponding place "as is"

$ \begin{align} 0\ 1\ 1\ 1\ \ \ \ \ 0\ 1\ 0\ 1\ \ \ \ \ 1\ 1\ 0\ 0\ \ \ \ \\ 8\ 4\ 2\ 1\ \ \ \ \ 8\ 4\ 2\ 1\ \ \ \ \ 8\ 4\ 2\ 1\ \ \ \ \\ \hline \\ 0\ 4\ 2\ 1\ \ \ \ \ 0\ 4\ 0\ 1\ \ \ \ \ 8\ 4\ 0\ 0\ \ \ \ \end{align} $

Add each set of four digits and write the sum below them.
$8 + 4 + 0 + 0 = 12$
But, $12 = C_{16}$
$0 + 4 + 0 + 1 = 5$
$0 + 4 + 2 + 1 = 7$

$ \begin{align} 0\ 1\ 1\ 1\ \ \ \ \ 0\ 1\ 0\ 1\ \ \ \ \ 1\ 1\ 0\ 0\ \ \ \ \\ 8\ 4\ 2\ 1\ \ \ \ \ 8\ 4\ 2\ 1\ \ \ \ \ 8\ 4\ 2\ 1\ \ \ \ \\ \hline \\ \quad \underbrace{0\ 4\ 2\ 1}\ \ \ \ \underbrace{0\ 4\ 0\ 1}\ \ \ \underbrace{8\ 4\ 0\ 0}\ \ \ \\ \underbrace{7}\ \qquad \underbrace{5}\ \qquad \underbrace{C}\ \ \ \ \end{align} \\[3ex] $ ∴ $\therefore 11101011100_2 = 75C_{16}$

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

This means that $ABBA$ 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$

$ ABBA_{16} \\[3ex] = 10 * 16^3 + 11 * 16^2 + 11 * 16^1 + 10 * 16^0 \\[3ex] = 10 * 4096 + 11 * 256 + 11 * 16 + 10 * 1 \\[3ex] = 40960 + 2816 + 176 + 10 \\[3ex] \therefore ABBA_{16} = 43962 \\[3ex] DEC \rightarrow BIN \\[3ex] \begin{array}{c|c} 2 & 43962 \\ \hline 2 & 21981 \:R\: 0 \\ \hline 2 & 10990 \:R\: 1 \\ \hline 2 & 5495 \:R\: 0 \\ \hline 2 & 2747 \:R\: 1 \\ \hline 2 & 1373 \:R\: 1 \\ \hline 2 & 686 \:R\: 1 \\ \hline 2 & 343 \:R\: 0 \\ \hline 2 & 171 \:R\: 1 \\ \hline 2 & 85 \:R\: 1 \\ \hline 2 & 42 \:R\: 1 \\ \hline 2 & 21 \:R\: 0 \\ \hline 2 & 10 \:R\: 1 \\ \hline 2 & 5 \:R\: 0 \\ \hline 2 & 2 \:R\: 1 \\ \hline 2 & 1 \:R\: 0 \\ \hline & 0 \:R\: 1 \end{array} \text{Count the remainders upwards} \\[3ex] 43962 = 1010101110111010_2 \\[3ex] $ ∴ $ABBA_{16} = 1010101110111010_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$
$ABBA_{16}$
We begin from behind
$A = 1010$
$B = 1011$
$B = 1011$
$A = 1010$
We write it upwards (beginning from the bottom)
$1010 \:1011\: 1011\: 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 ABBA_{16} = 1010101110111010_2$

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} \text{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} \text{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$

This means that $3AC1$ 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] 3AC1_{16} \\[3ex] = 3 * 16^3 + 10 * 16^2 + 12 * 16^1 + 1 * 16^0 \\[3ex] = 3 * 4096 + 10 * 256 + 12 * 16 + 1 * 1 \\[3ex] = 12288 + 2560 + 192 + 1 \\[3ex] \therefore 3AC1_{16} = 15041 \\[3ex] DEC \rightarrow BIN \\[3ex] \begin{array}{c|c} 2 & 15041 \\ \hline 2 & 7520 \:R\: 1 \\ \hline 2 & 3760 \:R\: 0 \\ \hline 2 & 1880 \:R\: 0 \\ \hline 2 & 940 \:R\: 0 \\ \hline 2 & 470 \:R\: 0 \\ \hline 2 & 235 \:R\: 0 \\ \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} \text{Count the remainders upwards} \\[3ex] 15041 = 11101011000001_2 \\[3ex] $ ∴ $3AC1_{16} = 11101011000001_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$
$3AC1_{16}$
We begin from behind
$1 = 0001$
$C = 1100$
$A = 1010$
$3 = 0011$
We write it upwards (beginning from the bottom)
$0011 \:1010\: :1100\: 0001$
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 two leading zeros.
$11 \:1010\: :1100\: 0001$

∴ $\therefore 3AC1_{16} = 11101011000001_2$

First Method: Operate in Base Two
We shall do our multiplication the usual way we multiply numbers.
Remember that Multiplication is Repeated Addition.

$ \begin{align} 1\ \ 0\ \ 0\ \ 0\ \ 1\ \ 1\ \ 1\ \ \\ * \ \ 1\ \ 1\ \ 1\ \ 1\ \ 0\ \ 0\ \ 0\ \ \\ \hline \end{align} \\[3ex] $ The minuend = $1000111$
It is seven digits
The subtrahend = $1111000$
It is also seven digits
Line them up
Do the multiplications
Do the additions

$ \begin{align} 1\ \ 0\ \ 0\ \ 0\ \ 1\ \ 1\ \ 1\ \ \\ * \ \ 1\ \ 1\ \ 1\ \ 1\ \ 0\ \ 0\ \ 0\ \ \\ \hline 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ \\ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0~~~~\ \ \\ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0~~~~~~~~\ \ \\ + \ \ \ \ \ \ \ \ \ \ 1\ \ 0\ \ 0\ \ 0\ \ 1\ \ 1\ \ 1~~~~~~~~~~~~\ \ \\ 1\ \ 0\ \ 0\ \ 0\ \ 1\ \ 1\ \ 1~~~~~~~~~~~~~~~~\ \ \\ 1\ \ 0\ \ 0\ \ 0\ \ 1\ \ 1\ \ 1~~~~~~~~~~~~~~~~~~~~\ \ \\ 1\ \ 0\ \ 0\ \ 0\ \ 1\ \ 1\ \ 1~~~~~~~~~~~~~~~~~~~~~~~~\ \ \\ \hline 1\ \ 0\ \ 0\ \ 0\ \ 0\ \ 1\ \ 0\ \ 1\ \ 0\ \ 0\ \ 1\ \ 0\ \ 0\ \ 0~~ \\ \hline \\[3ex] \end{align} $ ∴ $1000111_2 * 1111000_2 = 10000101001000_2$

Second Method: Convert to Base Ten, Operate in Base Ten, Convert to Base Two

$ \underline{Convert\;\;to\;\;Base\;\;Ten} \\[3ex] 1000111_2 \\[3ex] = 1 * 2^6 + 0 * 2^5 + 0 * 2^4 + 0 * 2^3 + 1 * 2^2 + 1 * 2^1 + 1 * 2^0 \\[3ex] = 1(64) + 0 + 0 + 0 + 1(4) + 1(2) + 1(1) \\[3ex] = 64 + 4 + 2 + 1 \\[3ex] = 71 \\[5ex] 1111000_2 \\[3ex] = 1 * 2^6 + 1 * 2^5 + 1 * 2^4 + 1 * 2^3 + 0 * 2^2 + 0 * 2^1 + 0 * 2^0 \\[3ex] = 1(64) + 1(32) + 1(16) + 1(8) + 0 + 0 + 0 \\[3ex] = 64 + 32 + 16 + 8 \\[3ex] = 120 \\[5ex] \underline{Operate\;\;in\;\;Base\;\;Ten} \\[3ex] 71 * 120 = 8520 \\[5ex] \underline{Convert\;\;to\;\;Base\;\;Two} \\[3ex] \begin{array}{c|c} 2 & 8520 \\ \hline 2 & 4260 \:R\: 0 \\ \hline 2 & 2130 \:R\: 0 \\ \hline 2 & 1065 \:R\: 0 \\ \hline 2 & 532 \:R\: 1 \\ \hline 2 & 266 \:R\: 0 \\ \hline 2 & 133 \:R\: 0 \\ \hline 2 & 66 \:R\: 1 \\ \hline 2 & 33 \:R\: 0 \\ \hline 2 & 16 \:R\: 1 \\ \hline 2 & 8 \:R\: 0 \\ \hline 2 & 4 \:R\: 0 \\ \hline 2 & 2 \:R\: 0 \\ \hline 2 & 1 \:R\: 0 \\ \hline & 0 \:R\: 1 \end{array} \text{Count the remainders upwards} \\[3ex] 8520 = 11000100100011000_2 \\[3ex] $ ∴ $1000111_2 * 1111000_2 = 10000101001000_2$

First Method: Operate in Base Two

$ \begin{align} 1\ \ 0\ \ 0\ \ 0\ \ 1\ \ 1\ \ 1\ \ \\ + \ \ 1\ \ 1\ \ 1\ \ 1\ \ 0\ \ 0\ \ 0\ \ \\ \hline \end{align} \\[3ex] $ The augend = $1000111$
It is seven digits
The addend = $1111000$
It is also seven digits
Line them up
Add each digit of the augend to the corresponding digit of the addend
Begin from the left

$ 1 + 0 = 1 \\[3ex] 1 + 0 = 1 \\[3ex] 1 + 0 = 1 \\[3ex] 0 + 1 = 1 \\[3ex] 0 + 1 = 1 \\[3ex] 0 + 1 = 1 \\[3ex] 1 + 1 = 2 = 10 \: (Remember \:that\: 2 = 10_2) \\[3ex] $ Write the result upwards beginning from the bottom
This gives: $10111111$

$ \begin{align} \ \ 1\ \ 0\ \ 0\ \ 0\ \ 1\ \ 1\ \ 1\ \ \\ + \ \ \ \ 1\ \ 1\ \ 1\ \ 1\ \ 0\ \ 0\ \ 0\ \ \\ \hline 1\ \ 0\ \ 1\ \ 1\ \ 1\ \ 1\ \ 1\ \ 1~~ \\ \hline \\[3ex] \end{align} $ ∴ $1000111_2 + 1111000_2 = 10111111_2$

Second Method: Convert to Base Ten, Operate in Base Ten, Convert to Base Two

$ \underline{Convert\;\;to\;\;Base\;\;Ten} \\[3ex] 1000111_2 \\[3ex] = 1 * 2^6 + 0 * 2^5 + 0 * 2^4 + 0 * 2^3 + 1 * 2^2 + 1 * 2^1 + 1 * 2^0 \\[3ex] = 1(64) + 0 + 0 + 0 + 1(4) + 1(2) + 1(1) \\[3ex] = 64 + 4 + 2 + 1 \\[3ex] = 71 \\[5ex] 1111000_2 \\[3ex] = 1 * 2^6 + 1 * 2^5 + 1 * 2^4 + 1 * 2^3 + 0 * 2^2 + 0 * 2^1 + 0 * 2^0 \\[3ex] = 1(64) + 1(32) + 1(16) + 1(8) + 0 + 0 + 0 \\[3ex] = 64 + 32 + 16 + 8 \\[3ex] = 120 \\[5ex] \underline{Operate\;\;in\;\;Base\;\;Ten} \\[3ex] 71 + 120 = 191 \\[5ex] \underline{Convert\;\;to\;\;Base\;\;Two} \\[3ex] \begin{array}{c|c} 2 & 191 \\ \hline 2 & 95 \:R\: 1 \\ \hline 2 & 47 \:R\: 1 \\ \hline 2 & 23 \:R\: 1 \\ \hline 2 & 11 \:R\: 1 \\ \hline 2 & 5 \:R\: 1 \\ \hline 2 & 2 \:R\: 1 \\ \hline 2 & 1 \:R\: 0 \\ \hline & 0 \:R\: 1 \end{array} \text{Count the remainders upwards} \\[3ex] 191 = 10111111_2 \\[3ex] $ ∴ $1000111_2 + 1111000_2 = 10111111_2$

$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} \text{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} \text{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} \text{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?
Let us save some time

$ 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} \text{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$