<s>[INST] What is the shortest way to compute the last 3 digits of $17^{256}$? What is the shortest way to compute the last 3 digits of $17^{256}$ ?
My solution:
\begin{align}
17^{256} &=289^{128} \\
&=(290 - 1)^{128}\\
&=\binom{128}{0}290^{128} -  ... +\binom{128}{126}290^2 - \binom{128}{127}290 + \binom{128}{128}
\end{align}
Computed the last 3 terms whose last 3 digits gave the last 3 digits of $17^{256}$.
Is there any shorter method to do this(which requires much less computation) ? 
 [/INST] Use Euler's Totient Theorem and the Chinese Remainder Theorem.
We have that $ 17 \equiv 1 \mod 8 $ and hence $ 17^{256} \equiv 1 \mod 8 $ as well.
Because $ 17 $ is coprime to $ 125 $, we know that $ 17^{100} \equiv 1 \mod 125 $.
We are left to calculate $ 17^{56} \mod 125 $, which can be quickly be done by hand via the method of doubling: $$\begin{align*} 17^{2} &\equiv 39 &\mod 125 \\ 17^4 &\equiv 21 &\mod 125\\ 17^8 &\equiv 66 &\mod 125\\ 17^{16} &\equiv 106 &\mod 125\\ 17^{32} &\equiv 111 &\mod 125 \end{align*}$$
Hence, $ 17^{32 + 16 + 8} \equiv 111 \cdot 106 \cdot 66 \equiv 56 \mod 125 $.
Using the Chinese Remainder Theorem, we have that the list three digits are $ 681 $.
</s>