Question

Use Algorithm 5 to find $3^{2003}mod99$

Short answer

$3^{2003}mod99=27$

Step-by-step solution

Step 1

Given

$3^{2003}mod99$

Let us first determine the binary expansion of 2003.

$2003=(11111010011{)}_2$

$a_1$then represents the iith digit in the binary expansion of 2003

$$\begin{gathered} a_0=a_1=a_4=a_6=a_7=a_8=a_9=a_{10}=1 \\ {a}_2=a_3=a_5=0 \end{gathered}$$

Initially x is set to 1 and power is set to 3mod99

$$\begin{gathered} x=1 \\ \text{power}=3mod99=3 \end{gathered}$$

Step 2

When $a_i=1$ then x is first multiplied by the power and reduced modulo 99

Then on each iteration the power is multiplied by itself and reduced modulo 99.

$$\begin{gathered} \mathbf{i}=\mathbf{0}{\text{Sincea}}_0=1 \\ x=1.3mod99=3mod99=3 \\ \text{power}=3^{2}mod99=9mod99=9 \\ \mathbf{i}=\mathbf{1}{\text{Sincea}}_1=1: \\ x=3.9mod99=27mod99=27 \\ \text{power}=9^{2}mod99=81mod99=81 \\ \begin{array}{r}\mathbf{i}=\mathbf{2}\mathrm{Sin}{\mathrm{cea}}_2=0:\\ \\ x=27\\ \\ \text{power}={81}^{2}mod99=6561mod99=27\end{array} \end{gathered}$$

role="math" localid="1668517890384" $\begin{array}{r}x=27\\ \\ \text{power}={27}^{2}mod99=729mod99=36\\ \\ \mathbf{i}=\mathbf{4}{\text{Sincea}}_4=1:\\ \\ x=27\cdot 36mod99=972mod99=81\\ \\ \text{power}={36}^{2}mod99=1296mod99=9\\ \\ \mathbf{i}=\mathbf{5}{\text{Sincea}}_5=0\\ \\ x=81\\ \\ \text{power}=9^{2}mod99=81mod99=81\\ \\ \mathbf{i}=\mathbf{6}{\text{sincea}}_6=1:\\ \\ x=81\cdot 81mod99=6561mod99=27\\ \\ \text{power}={81}^{2}mod99=6561mod99=27\end{array}$

Step 3

$\begin{array}{r}\mathbf{i}=7{\text{Sincea}}_7=1:\\ \\ x=27\cdot 27mod99=729mod99=36\\ \\ \text{power}={27}^{2}mod99=729mod99=36\\ \\ \mathbf{i}=\mathbf{8}{\text{Sincea}}_8=1:\\ \\ x=36\cdot 36mod99=1296mod99=9\\ \\ \text{power}={36}^{2}mod99=1296mod99=9\\ \\ \mathbf{i}=\mathbf{9}{\text{sincea}}_9=1:\\ \\ \text{return}{x}^x=27\\ \\ \text{power}={81}^{2}mod99=6561mod99=27\\ \\ \text{power}=9^{2}mod99=81mod99=81\\ \\ \mathbf{i}=\mathbf{10}{\text{Sincea}}_{10}=1:\\ \\ x=81\cdot 81mod99=6561mod99=27\\ \\ mod99=81\end{array}$