1642^899 mod 2257
You asked:
MathBot Answer:
\[{1642}^{899} \bmod 2257 = 378\]
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 \(899\) is \(\mathtt{\text{1110000011}}\). 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 \(2257\).
- If the digit is 1, square the result from the previous row and calculate the result modulo \(2257\). Multiply that result by the base and calculate the result of that operation modulo \(2257\).
The result corresponding to the last digit in the binary representation is the answer.$$\begin{aligned}\mathtt{\text{1}}&\,\,\,|\,\, 1642\\\mathtt{\text{1}}&\,\,\,|\,\, 1642^2 \bmod 2257 = 1306, 1306 \cdot 1642 \bmod 2257 = 302\\\mathtt{\text{1}}&\,\,\,|\,\, 302^2 \bmod 2257 = 924, 924 \cdot 1642 \bmod 2257 = 504\\\mathtt{\text{0}}&\,\,\,|\,\, 504^2 \bmod 2257 = 1232\\\mathtt{\text{0}}&\,\,\,|\,\, 1232^2 \bmod 2257 = 1120\\\mathtt{\text{0}}&\,\,\,|\,\, 1120^2 \bmod 2257 = 1765\\\mathtt{\text{0}}&\,\,\,|\,\, 1765^2 \bmod 2257 = 565\\\mathtt{\text{0}}&\,\,\,|\,\, 565^2 \bmod 2257 = 988\\\mathtt{\text{1}}&\,\,\,|\,\, 988^2 \bmod 2257 = 1120, 1120 \cdot 1642 \bmod 2257 = 1842\\\mathtt{\text{1}}&\,\,\,|\,\, 1842^2 \bmod 2257 = 693, 693 \cdot 1642 \bmod 2257 = 378\end{aligned}$$The answer is \(378\).