<s>[INST] 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?
 [/INST] 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$
</s>