$n=(2^{2014}-1)/3$ what is the remainder when it is divided by $1000$. i wrote $2$ as $3-1$ and proceeded but that only helped me prove $n$ is a integer but i dont know how to find the remainder on dividing it by 1000. well im guessing it involves some number theory theorom. please guide me.(i was thinking of using euler totient theorom but could not do so)
Answer
Without being clever, let's brute force our way through.
We want to understand $2^{2014} - 1 \pmod{1000}$. Notice that $\gcd(3,1000) = 1$, so $3$ has a modular inverse (a quick check shows that it's $667$).
Now, how do we find $2^{2014} - 1 \pmod {1000}$? As $\gcd(2,1000) = 2$, we should worry about the $2$ factor. So we think of $1000$ as $2^3 \cdot 5^3$.
Clearly $2^{2014} \equiv 0 \pmod {2^3}$. And as $\varphi(5^3) = 100$, we know that $2^{2014} \equiv 2^{14} \equiv 9 \pmod {125}$. Putting these together, perhaps with the Chinese Remainder Theorem or by quick brute force (there are only 8 things to check, afterall), we see that $2^{2014} \equiv 384 \pmod{1000}$.
Thus $2^{2014} - 1 \equiv 383 \pmod{1000} $. And thus $\frac{2^{2014}-1}{3} \equiv 667\cdot(2^{2014}-1) \equiv 667 \cdot 383 \equiv 461 \pmod{1000}$.
So the remainder is $461$.
No comments:
Post a Comment