solving a congruence modulo $1002$

Question

My question is about number theory, about congruences.

I need to solve the congruence $2^{1002}$ modulo $1002$.

I try to apply Chinese remainder,

Fermat's little theorem

and a few theorems more but i think i am on the wrong way:(

I need a hint to start the solution i think...

$2^{1002}$ is congruent to which number modulo $1002$?

Thanks for your help...

Answer 1

Here is my take: 1002 = 3 *2 * 167

Reminder by 6 (apply Chinese) = 4 Reminder by 167 (apply fermat's ) = 64

So reminder by 1002 (apply Chinese again) = 64.

Answer 2

Use $a^n \bmod m = a^{(n \;\bmod \; \varphi(m))} \bmod m$, where $\varphi$ is the Euler totient function. Since $1002 = 2 \times 3 \times 167$ we have $\varphi(1002)=1\times 2 \times 166= 332$. Therefore $$2^{1002} \equiv 2^{(1002 \;\bmod \; 332)} \equiv 2^6 \equiv 64 \pmod{1002} $$