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) ? 
 A: Your way seems to be the fastest for me
$$\binom{128}{128}=1\equiv1\mod{1000}$$
$$\binom{128}{127}=128\equiv28\pmod{100}$$
$$\implies  \binom{128}{127}290\equiv 28\cdot290\pmod{1000}\equiv120$$
$$\binom{128}{126}=\frac{128\cdot127}2\equiv8\pmod{10}$$
$$\implies \binom{128}{126}290^2\equiv 290^2\cdot8\pmod{1000}\equiv800 $$
Using $a\equiv b\pmod m\implies a\cdot c\equiv b\cdot c\pmod {c\cdot m}$ where $a,b,c,m$ are integers
A: 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 $.
A: I am not sure what "shorter" means, but $\phi(1000) = 400,$ so $17^{400} = 1,$ so $17^{200} = \pm 1,$ so you only need to compute $17^{56}.$ Since you don't know which one of $\pm 1$ to take, you have two possible answers, but to know which one is right, look at the last digit.
A: HINT:
As $1000=125\cdot8$
$$17\equiv1\pmod8\implies 17^n\equiv1\pmod8$$
Now, $\phi(125)=100\implies 17^{256}\equiv17^{56}\pmod{125}$
Then apply CRT
