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

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?

• 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). – lulu Feb 9 '20 at 18:04
• but how is $(2^{2017}+1)*667$ (mod $1000$) any easier to solve? am I missing something obvious? – Silverleaf1 Feb 9 '20 at 18:09
• Well, $2^{2017}\pmod {1000}$ can be computed by iterated squaring, not too bad. You need that anyway, for the first term. – lulu Feb 9 '20 at 18:13
• 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}$. – lulu Feb 9 '20 at 18:22

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

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

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

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