How to find mod for $19^{33} \pmod{20413}$?

Question

Struggling to understand how to answer this question as the formula previously used required n to be a multiple of the previous number, which as 33 is involved this method is no longer effective. From the mark scheme the answer to the question should be 6338.

Appreciate the help

Answer 1

Using my 9-digit handheld calculator and following this answer, $$19^2=361$$ $$19^4=361^2=130321\equiv 7843 \pmod {20413}$$ $$19^8\equiv 7843^2 \equiv 8280 \pmod {20413}$$ $$19^{16}\equiv 8280^2\equiv 11546 \pmod {20413}$$ $$19^{32}\equiv11546^2\equiv13226\pmod{20413}$$ Therefore, $19^{33}\equiv 19\times13226 \equiv 251294\equiv6338\pmod {20413}. $

Answer 2

We factor $20413=137\cdot 149.$ Compute $19^{33}\bmod {137}$ and $19^{33}\bmod{149}$ then use Chinese Remainder Theorem to find $19^{33}\bmod{137\cdot 149}.$

We can find $19^{33}\bmod {137}$ by the method of repeated squaring.$$\begin{align}19^2&=361&\equiv -50\pmod{137}\\ 19^4&\equiv (-50)^2 = 2500 &\equiv 34\pmod{137}\\ 19^8&\equiv 34^2 = 1156 &\equiv 60\pmod{137}\\ 19^{16}&\equiv 60^2=3600 &\equiv 38\pmod{137}\\ 19^{32}&\equiv 38^2=1444&\equiv 74\pmod{137}\\ 19^{33}&=19\cdot 19^{32}\equiv 19\cdot 74=1406&\equiv 36\pmod{137} \end{align}$$

Similarly, you can compute $19^{33}\bmod 149=80.$ Then solve the equation:

$$\begin{align}x&\equiv 36\pmod{137}\\x&\equiv 80\pmod{149}\end{align}$$

using Chinese Remainder Theorem, and this will give you $x\equiv 6338\pmod{137\cdot 149}.$

Assuming you could not reasonably factor the modulus, $M=20413,$ you could have just done one case of repeated squaring, modulo $M.$ The squaring will be harder, but you'll only have to do it once, and you do not have to do Chinese Remainder Theorem, nor factor $M.$

Answer 3

Square and multiply by $19$ the result given in your previous question on $\,19^{\large 16}\bmod 20413$.