Find the remainder when $2^{2019}$ is divided by $2019$

Question

This question is from Jmo odisha 2019. I used fermat's theorem but it did not work as 2019 is a composite number. Then how do I solve it?

Answer 1

Using Euler's theorem, $2^{1344}\equiv1\bmod2019$, so $2^{2019}\equiv2^{675}\bmod2019$.

By Fermat's little theorem, $2^{672}\equiv1\bmod673$, so $2^{675}\equiv2^3=8\bmod673$.

Also $2^{675}\equiv2^1\equiv2^3=8\bmod3$.

Therefore, by the Chinese remainder theorem, $2^{675}\equiv8\bmod2019$.

---

More generally, if $p>3$ is prime, then $p$ divides $2^{p-1}-1,$ and $3$ divides $2^{p-1}-1,$

so $3p$ divides $2^{p-1}-1$, so $3p$ divides $2^{3p-3}-1$, so $3p$ divides $2^{3p}-8$.

Answer 2

Or, $2^{2019}\cong2\pmod3$ and $2^{2019}\cong2^3\pmod{673}$, both by little fermat.

Then since $2\cong2^3\pmod3$, we can use the constant case of the Chinese remainder theorem.

Thus $2^{2019}\cong8\pmod{2019}$.