What is the remainder when $2^{2016}+ 1009^{2016}$ is divided by $2019$?

Question

What is the remainder when $2^{2016} + 1009^{2016}$ is divided by $2019$? The answer is $2$, but I am struggling to prove it. Please help.

Answer 1

By Euler's theorem $$2^{1344} \equiv 1\ (\text {mod}\ 2019).$$ Observe also by Euler's theorem that $$\begin{align*} 2^{672} &\equiv 1\ (\text {mod}\ 673).\end{align*}$$ and $$2^{672} \equiv 1\ (\text {mod}\ 3)$$

So we have $$\begin{align*} 2^{672} & \equiv 1\ (\text {mod}\ \text {lcm}\ (3,673)). \\ & \equiv 1\ (\text {mod}\ 2019). \end{align*}$$

Therefore $$\begin{align*} 2^{2016} & \equiv 2^{1344} \cdot 2^{672}\ (\text {mod}\ 2019). \\ & \equiv 1\ (\text {mod}\ 2019). \end{align*}$$

Also by Euler's theorem we have $$1009^{1344} \equiv 1\ (\text {mod}\ 2019)$$ and we also have $$1009^{672} \equiv 1\ (\text {mod}\ 3)$$ and $$1009^{672} \equiv 1\ (\text {mod}\ 673).$$ So $$\begin{align*} 1009^{672} & \equiv 1\ (\text {mod}\ \text {lcm}\ (3,673)). \\ & \equiv 1\ (\text {mod}\ 2019). \end{align*}$$

So $$\begin{align*} 1009^{2016} & \equiv 1009^{1344} \cdot 1009^{672}\ (\text {mod}\ 2019) \\ & \equiv 1\ (\text {mod}\ 2019). \end{align*}$$

Now observe that $$\begin {align*} 2018^{2016} & \equiv (-1)^{2016}\ (\text {mod}\ 2019)\\ & \equiv 1\ (\text {mod}\ 2019) \end{align*}$$

So we have $$2^{2016} + 1009^{2016} + 2018^{2016} \equiv 3\ (\text {mod}\ 2019).$$

Answer 2

Use http://mathworld.wolfram.com/CarmichaelFunction.html,

$\lambda(2019)=$lcm$(2,672)=672$

If $(a,2019)=1,a^{672}\equiv1\pmod{2019}$

and $2016\equiv0\pmod{672}$