<s>[INST] How to efficiently compute $\,25^{37}\pmod{55}$? Most efficient way to do this question?
$25^{37}\cong (mod 55)$
Attempt:
$25^2 \cong 20 (mod55)$
Then I don't know the best way to continue... I know how to brute force it but I'm just curious what the best way is?
 [/INST] First, $55 = 5 \cdot 11$ and $(5,11) = 1$, so we will use the Chinese remainder theorem to assemble the result after working modulo $5$ and $11$, separately.
Modulo $5$, $25 \cong 0$, so $25^{37} \cong 0 \pmod{5}$.
Modulo $11$, $25 \cong 3$ and (using Fermat's little theorem) $37 \cong 7 \pmod{10}$, so we compute
$$  25^{37} \cong 3^{37} \cong 3^7 \pmod{11}  \text{.}  $$
Then \begin{align*}
    3^{7} &\cong 3^8 \cdot 3^{-1} \pmod{11}  \\
    &\cong ((3^2)^2)^2 \cdot 3^{-1} \pmod{11}  \\
    &\cong (9^2)^2 \cdot 3^{-1} \pmod{11}  \\
    &\cong 4^2 \cdot 3^{-1} \pmod{11}  \\
    &\cong 5 \cdot 3^{-1} \pmod{11}  \\
    &\cong 5 \cdot 4 \pmod{11}  \\
    &\cong 9 \pmod{11}  \text{.}
\end{align*}
Then, using the CRT, we want a multiple of $5$ that is congruent to $9$ modulo $11$.  Check sequentially: $5$, $10$, $15$, $20$.  We find that $20$ works.  (There are direct methods, but it's easy to work through the (at most) eleven multiples of $5$.)
Our answer is $25^{37} \cong 20 \pmod{55}$.
</s>