Any other quick way to find the remainder?

Question

I want to find $$19^{13}\operatorname{mod}(2537).$$

Is there quick way to find the remainder?

Answer 1

HINT:

• Write $19^{13}=(19^3)^4\cdot19$.

• Note that $19^3=6859\equiv-752\pmod{2537}$.

• Write $(-752)^4$ as $((-752)^2)^2$ and evaluate the inner bracket to simplify.

Answer 2

\begin{eqnarray} 19^3=6859&\equiv& 1785(\operatorname{mod}2537)\\ 19^6=\left(19^3\right)^2\equiv (1785)^2=3186225&\equiv& 2290(\operatorname{mod}2537)\\ 19^{12}=\left(19^6\right)^2\equiv (2290)^2 = 5244100&\equiv& 121(\operatorname{mod}2537)\\ 19^{13}=19^{12}\cdot19&\equiv& 121\cdot 19=2299(\operatorname{mod}2537) \end{eqnarray}

So the remainder is 2299. Is this correct answer?