2
$\begingroup$

After simplifying $\frac{2^{2017}+1}{3\cdot 2^{2017}}$ to $\frac{n}{m}$ where $n$ and $m$ are coprime, find the remainder when $m+n$ is divided by $1000$.

Since the top is odd and the bottom is even, the only thing that can cancel is the $3$. Therefore, I'm looking for $2^{2017}+\frac{2^{2017}+1}{3}$ (mod $1000$). However, I don't know how to find this value. Could someone give me a hint?

$\endgroup$
4
  • 1
    $\begingroup$ Good start. To finish, note that $3n\equiv 1 \pmod {1000}\implies n\equiv 667\pmod {1000}$, so you just want $(2^{2017}+1)\times 667\pmod {1000}$ (for the second term). $\endgroup$ – lulu Feb 9 '20 at 18:04
  • $\begingroup$ but how is $(2^{2017}+1)*667$ (mod $1000$) any easier to solve? am I missing something obvious? $\endgroup$ – Silverleaf1 Feb 9 '20 at 18:09
  • $\begingroup$ Well, $2^{2017}\pmod {1000}$ can be computed by iterated squaring, not too bad. You need that anyway, for the first term. $\endgroup$ – lulu Feb 9 '20 at 18:13
  • 1
    $\begingroup$ Even easier: it is easy to see that $2^{2017}\equiv 72 \pmod {5^3}$ which quickly shows that $2^{2017}\equiv 72\pmod {1000}$. $\endgroup$ – lulu Feb 9 '20 at 18:22
1
$\begingroup$

Clearly $\gcd (2^{2017}+1,2^{2017}3)=3$ so $$3m+3n =2^{2017}3+(2^{2017}+1)=2 ^{2019}+1$$

So $$3(m+n)\equiv _8 1$$ so $$m+n\equiv _8 3$$ and since $\varphi(125)=100$ we have by Euler theorem $$3(m+n)\equiv _{125} 2^{19}+1 = 2^9\cdot 2^{10}+1 \equiv _{125}39$$ $$ \implies m+n \equiv_{125} 42\cdot 39 \equiv_{125} 13$$

Write $m+n = 8x+3$ then we have $$125\mid 8x-10\implies 125\mid 4x-5 $$

$$\implies 125\mid 4x+120 = 4(x+30)\implies 125\mid x+30$$ so $x = 125y-30$ and thus $$ m+n = 1000y-237$$

So the answer is $\boxed{763}$.

$\endgroup$
0
0
$\begingroup$

We can write $3m=2^{2017}+1$ and $3n=3\cdot2^{2017}$

Now $3(m+n)=1+2^{2017}(1+3)=1+2^{2019}$

Now as $\phi(125)=100$ and $(2,125)=1$

Like How to find last two digits of $2^{2016}$

$2^{2016}\equiv2^{16}\equiv(2^8)^2\equiv6^2\pmod{125}$

$\implies2^{2016+3}\equiv2^36^2\pmod{125\cdot2^3}$

$\implies3(m+n)\equiv1+36\cdot8\pmod{1000}$

$\implies m+n\equiv289\cdot3^{-1}\equiv(96\cdot3+1)(3^{-1})\equiv96-333+1000$

as $3^{-1}\equiv1\equiv-333\equiv-333+1000$

$\endgroup$
0
0
$\begingroup$

$3*2^{2017}$ has only prime factors of $2$ and $3$ an $2^{2017} + 1$ is not divisible by $2$ so the only thing that can cancel out is $3$. But does $3$ cancel out?

$2 \equiv -1\pmod 3$ so $2^{2017} + 1\equiv (-1)^{2017}+ 1\equiv -1 + 1 \equiv 0\pmod 3$ so, yes, $3$ cancels out.

So $\frac mn = \frac {2^{2017} + 1}{3*2^{2017}}$ so $m = \frac {2^{2017}+1}3$ and $n = 2^{2017}$.

So we need to find $m + n\pmod{1000}$.

$1000 = 8*125$ and by $n = 2^{2017}=8*2^{2014}\equiv 0 \pmod 8$ and be Euler's Th: as $\phi(125) = \phi(5^3)= 4*5^2= 100$ we have $2^{2017}\equiv 2^{17}\pmod {125}$.

Now $3$ is relatively prime to $8$ and to $125$ so $3^{-1}\mod 8$ and $3^{-1}\mod 125$ exist. And $m = (2^{2017}+1)*3^{-1} \equiv 3^{-1}\pmod 8$ and $m\equiv (2^{2017}+1)3^{-1}\equiv (2^{17}+1)*3^{-1}\pmod {125}$.

So $m + n \equiv 3^{-1} \pmod 8$ and $m +n \equiv 2^{17} + (2^{17}*+1)*3^{-1} \pmod {125}$.

.....

Deep breath

.....

so we need to figure out $2^{17}\pmod{125}$ and $3^{-1}\pmod {125}$ and $3^{-1}\pmod 8$.

...

$1\equiv 9=3*3\pmod 8$ so $3^{-1}\equiv 3\pmod 8$ and $m+n\equiv 3\pmod 8$.

$2^7= 128 \equiv 3\pmod {125}$ and $2^{10}\equiv 1024\equiv 24\pmod {125}$ so $2^{17} \equiv 72\pmod {125}$.

And $1\equiv 126= 3*42\pmod {125}$ so $3^{-1}\equiv 42\pmod {125}$.

So $m+n \equiv 72 + (72+1)*42\equiv 3138\equiv 13\pmod{125}$.

....

So $m+n \equiv 3\pmod 8$ and $m+n \equiv 13\pmod {125}$.

Now we need

$3 + 8m = 13 + 125k$

$8m = 10 + (8*15 + 5)k$

$8(m-15k) = 10 + 5k$

$8(m-15k) = 5(k+2)$

$m-15k = k+2 = 0$ will do.

$k=-2$ and $m=-30$ or

$3-8*30 = -237$ and $13-125*2=-237\equiv 763\pmod{1000}$

So I get $763$

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