-1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Well, since $2^{50}\equiv -1\pmod {125}$ we have $2^{100}\equiv 1 \pmod {125}$ which implies $2^{2017}\equiv 2^{17}\pmod {125}$. Can you finish from there? $\endgroup$ – lulu May 19 at 23:41
  • $\begingroup$ note: $2^{17}=131072$ $\endgroup$ – J. W. Tanner May 19 at 23:45
  • $\begingroup$ It seems what you are missing is the notion of modular order reduction on exponents. Once you know that $2^{100}\equiv 1$ then you can reduce $\bmod 100$ all exponents on powers of $2$ - see the comment on my answer (this is essentially what is being done implicitly in Don's answer, but it is best to make the idea more explicit in order to best master it). $\endgroup$ – Gone May 20 at 1:00
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Did you mean $2^{50}\equiv\color{red}-1\bmod125$? $\endgroup$ – J. W. Tanner May 19 at 23:50
  • $\begingroup$ But how do you propose to easily compute the value of $\,2^{\large 50}\bmod 125?\ \ $ $\endgroup$ – Gone May 20 at 0:10
  • 1
    $\begingroup$ @Gone See OP's post. $\endgroup$ – Don Thousand May 20 at 0:19
  • $\begingroup$ @Don That's not particularly easy mentally. $\endgroup$ – Gone May 20 at 0:23
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ We used modular order reduction to reduce the exponent on $\,2\,$ from $\,2017\,$ to $\ 2017\bmod 100 = \color{#c00}{17}.\ $ The entire solution takes $< 30$ seconds of mental arithmetic (and no CRT is required). $\endgroup$ – Gone May 20 at 1:03
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.