What is the shortest way to compute the last 3 digits of $17^{256}$?

Question

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) ?

Answer 1

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

Answer 2

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.

Answer 3

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

Answer 4

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 $.