¿Alguna otra forma rápida de encontrar el resto?

Question

Quiero encontrar $$19^{13}\operatorname{mod}(2537).$$

¿Hay alguna forma rápida de encontrar el resto?

Answer 1

SUGERENCIA:

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

• Tenga en cuenta que $19^3=6859\equiv-752\pmod{2537}$ .

• Escriba $(-752)^4$ como $((-752)^2)^2$ y evaluar el paréntesis interior para simplificar.

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}

Así que el resto es 2299. ¿Es esta la respuesta correcta?