21^19 mod 59
You asked:
MathBot Answer:
\[{21}^{19} \bmod 59 = 46\]
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 \(19\) is \(\mathtt{\text{10011}}\). 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 \(59\).
- If the digit is 1, square the result from the previous row and calculate the result modulo \(59\). Multiply that result by the base and calculate the result of that operation modulo \(59\).
The result corresponding to the last digit in the binary representation is the answer.$$\begin{aligned}\mathtt{\text{1}}&\,\,\,|\,\, 21\\\mathtt{\text{0}}&\,\,\,|\,\, 21^2 \bmod 59 = 28\\\mathtt{\text{0}}&\,\,\,|\,\, 28^2 \bmod 59 = 17\\\mathtt{\text{1}}&\,\,\,|\,\, 17^2 \bmod 59 = 53, 53 \cdot 21 \bmod 59 = 51\\\mathtt{\text{1}}&\,\,\,|\,\, 51^2 \bmod 59 = 5, 5 \cdot 21 \bmod 59 = 46\end{aligned}$$The answer is \(46\).