Find the last three digits of $17^{256}$ Find the last three digits of 
$ 17 ^{256} $
We have to check mod $1000$
 I tried to check some patterns but in vain.!
 A: As $1000=8\times 125$ comptute first $17^{256}$ modulo $8$ and modulo $256$, then use the Chinese Remainder Theorem to recover $17^{256}\mod 1000$.
Modulo $8$: $\enspace 17\equiv 1\mod 8$, hence $17^{256}\equiv 1 \mod 8$.
Modulo $125$:
By Euler's theorem, $n^{\varphi(125)}\equiv 1\mod125$ for all $n$. As $\varphi(125)=100$, we have $17^{256}=17^{56} \mod 125$. More over we can check $17^{50}\equiv -1 \mod 125$, hence:
$$17^{56}\equiv -17^6\equiv -69\equiv 56\mod 125.$$
$17^{256}\bmod 1000\,$ is the solution of the system of congruences:
$$\begin{cases}x\equiv 1\mod 8\\x\equiv 56\mod 125\end{cases}$$
The extended euclidean algorithm yields Bézout's identity:
   \begin{array}[t]{c@{\qquad}r@{\qquad}r@{\qquad}c}
  r_i & u_i & v_i  & q_i\\
   \hline
  125 & 1 & 0 & \\
  8 & 0 & 1 & 15\\
     \hline
 5 & 1 & -15 & 1 \\
 3 & -1 & 16 & 1\\
2 & 2 & -31 & 1 \\
 1 & -3 & 47 \\
     \hline
    \end{array} 
\begin{align*}&-3\times 125+47\times 8=1,\\
\text{whence}\quad x\equiv-3\times 125&\times\color{red}{1}+47\times 8 \times\color{red}{56}=20681\equiv \color{red}{681} \mod 1000.\end{align*}
