Last 3 digits of $2^{2017}$

Question

Find the last three digits of $2^{2017}$

My approach:

As $125 \times 8=1000$ we have the congruence modulo $$x \equiv 2^{2017}(mod \: 1000)$$ is equivalent to the equations $$x \equiv 2^{2017}(mod \:125) \tag{1}$$ and $$x \equiv 2^{2017}(mod\:8) \tag{2}$$

Clearly from $(2)$ $x=8m$

Now we need to find remainder when $2^{2017}$ is divided by $125$

We have:

$$2^7 \equiv 3(mod \:125)$$

so $$2^{49} \equiv 3^7(mod \:125)\equiv -63(mod \:125)$$

Hence $$2^{50}\equiv -1(mod \:125) \tag{3}$$

From $(3)$ how to find remainder when $2^{2017}$ is divided by $125$?

Answer 1

As @lulu noted in the comments, $2^{50}\equiv-1\bmod{125}$, as well as $2^7\equiv3\bmod{125}$ imply that $$2^{2017}=(2^{50})^{40}\cdot(2^7)^2\cdot2^3\equiv(-1)^{40}\cdot3^2\cdot8\bmod{125}$$$$2^{2017}\equiv72\bmod{125}$$

Answer 2

Using $\ ab\bmod ac = a(b\bmod c) = $ mod Distributive Law to factor out $\,a = 8\,$ yields

$\ \ \ 2^{\large 2017}\!\bmod 1000 = 8\left[\dfrac{2^{2017}}8\bmod 125\right] = 8\left[\dfrac{2^{\large\color{#c00}{17}}}8\bmod 125\right] = 8\left[\dfrac{\color{#0a0}{72}}8\bmod 125\right] = 72$

by Euler & $\,\color{#c00}{17} = 2017\bmod 100\!=\!\phi(125),\,$ & $\!\bmod 125\!:\ 2^{\large\color{#c00}{17}}\!\equiv 2(\color{#90f}{2^{\large 8}})^{\large 2}\!\equiv 2(\color{#90f}6)^{\large 2}\!\equiv\color{#0a0}{72}$

Answer 3

$\varphi(125)=100\stackrel{\text{Euler's theorem}}\implies 2^{100}\cong1\bmod {125}$. Thus we get $2^{2017}\cong2^{17}\bmod{125}\implies 2^{2017}\cong2^7\cdot2^{10}\cong3\cdot24\cong72\bmod{125}$.

Answer 4

Note: I wrote this answer to show how relations / tricks (c.f. wiki article Presentation of a group) can be found to solve these questions; I like working on these questions as puzzles.

We take it from the OP's

Now we need to find remainder when $2^{2017}$ is divided by $125$

So calculating

$\quad x \equiv 2^{2017} \pmod {125}$ and $0 \le x \lt 125$

Since $2^7 \equiv 3 \pmod {125}$,

$\quad x \equiv 2 \times 3^{288} \pmod {125}$

Since $3^4 \equiv -1 \times 4 \times 11 \pmod {125}$,

$\quad x \equiv 2 \times 2^{144} \times 11^{72} \pmod {125}$

Since $11^2 \equiv -4 \pmod {125}$,

$\quad x \equiv 2^{217} \pmod {125}$

Plowing along using our developed relations,

$\quad x \equiv {(2^{7})}^{31} \equiv 3^{31} \equiv 3^3 \times {(3^4)}^7 \equiv (-1) (3^3) (4^7) (11^7) \equiv (3^3)(2^{20}) (11) \equiv$
$\quad \quad (3^5)(2^{6}) (11) \equiv (-7) (-61) (11) \equiv (-61) (-77) \equiv 72 \pmod {125}$