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?
 A: 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}$.
A: You can use the Chinese Remainder Theorem, and Fermat's Little Theorem.
Observe that $55=5\times 11$. Clearly $25^{37}\equiv0\pmod5$. Also
$$25^{37}=5^{74}\equiv 5^4=25^2\equiv 3^2\equiv 9\pmod{11}$$
using $5^{10}\equiv1\pmod{11}$ (Fermat's Little Theorem). Using
the Chinese Remainder Theorem one gets $25^{37}\equiv20\pmod{55}$.
A: This answer is not as slick as the answers posted before mine.  But, this technique works for incredibly large powers even when you do NOT know how the modulus factors...
$37 = 1 + 4 + 32 = 2^0 + 2^2 + 2^5$ so record $25^{2^k} \bmod 55$ for $k=0, 1, \ldots, 5$, but get it by repeated squaring, which is fast:  $25^{2^{k+1}}=(25^{2^k})^2$.  Get, in order, 
$$
25, 20, 15, 5, 25, 20.
$$
Now multiply the entries corresponding to $k=0, 2, 5$ to get
$$
25 \cdot 15 \cdot 20 = 20.
$$
Hence $25^{37} = 20 \bmod 55$.
A: $$25^{37}=5^{74}$$
Now as $(5^n,55)=5$ for $n\ge1$
$$5^{74-1}\equiv5^{73\pmod{\phi(55/5)}}\pmod{55/5}$$
$$\implies5^{73}\equiv5^3\equiv4\pmod{11}$$
$$\implies5\cdot5^{73}\equiv5\cdot4\pmod{5\cdot11}$$
A: Note $\,5^{\large 74} \bmod 55 = \overbrace{5(5^{\large 3}(\color{#c00}{5^{\large 10}})^{\large 7} \bmod 11)}^{\Large  1\ \equiv\  \color{#c00}{5^{\Large 10}} \ {\rm by \ Euler}}  = 5(4)\ $ 
using $\,\ ab\bmod ac = a(b\bmod c) =$ mod Distributive Law to pull a factor of $\,5\,$ out of the $\!\bmod$
