208^91 mod 221
You asked:
MathBot Answer:
\[{208}^{91} \bmod 221 = 13\]
When dealing with an exponential expression, use the square-and-multiply algorithm to calculate the answer in a faster and easier way than evaluation and division.
First, find the binary representation of the exponent. The binary representation of \(91\) is \(\mathtt{\text{1011011}}\). Create rows corresponding to each digit of the binary representation.
Place the base in the row corresponding to the first binary digit. For each subsequent digit in the binary representation perform one of two operations:
- If the digit is 0, square the result from the previous row and calculate the result modulo \(221\).
- If the digit is 1, square the result from the previous row and calculate the result modulo \(221\). Multiply that result by the base and calculate the result of that operation modulo \(221\).
The result corresponding to the last digit in the binary representation is the answer.$$\begin{aligned}\mathtt{\text{1}}&\,\,\,|\,\, 208\\\mathtt{\text{0}}&\,\,\,|\,\, 208^2 \bmod 221 = 169\\\mathtt{\text{1}}&\,\,\,|\,\, 169^2 \bmod 221 = 52, 52 \cdot 208 \bmod 221 = 208\\\mathtt{\text{1}}&\,\,\,|\,\, 208^2 \bmod 221 = 169, 169 \cdot 208 \bmod 221 = 13\\\mathtt{\text{0}}&\,\,\,|\,\, 13^2 \bmod 221 = 169\\\mathtt{\text{1}}&\,\,\,|\,\, 169^2 \bmod 221 = 52, 52 \cdot 208 \bmod 221 = 208\\\mathtt{\text{1}}&\,\,\,|\,\, 208^2 \bmod 221 = 169, 169 \cdot 208 \bmod 221 = 13\end{aligned}$$The answer is \(13\).