How to calculate $1900^{13} \pmod{2537}$
I should be able to do this problem but I don't figure a fast way of calculating it.
Edit: I find reduced the problem to solve:
$X≡12^{13}$mod$59$ and $X≡2^{39}$mod$43$
and I don't know how to solve
$X≡12^{13}$mod$59$
To compute $p=12^{13}\bmod 59$, you can use the fast exponentiation algorithm (‘square and divide’):
\begin{array}{rlll} n&x& &p \\ \hline 13 & x=12& &p=12 \\ 6 &x^2=26&&\phantom{p={}}12 \\ 3& x^4=26^2=27&&p=27\cdot 12=29 \\ 1&x^8=27^2=21&&p=21\cdot 29=\color{red}{19} \\ \hline \end{array}
As to $2^{39}\bmod 43$, by lil' Fermat, it is $2^{-3}=8^{-1}$, and the extended Euclidean algorithm yields in a few steps that $$8^{13}=-22.$$