What is the remainder when $2^{1990}$ is divided by $1990$?

Solution 1:

Using Fermat's Little Theorem,

$2^4\equiv1\pmod 5\implies 2^{1990}=2^2\cdot(2^4)^{997}\equiv4\cdot1^{997}\pmod 5\equiv4\ \ \ \ (1)$

$2^{198}\equiv1\pmod {199}\implies 2^{1990}=2^{10}\cdot(2^{198})^{10}\equiv1024\cdot1^{10}\pmod{199}\equiv 29\ \ \ \ (2)$

Clearly, $2^{1990}\equiv0\pmod2\ \ \ \ (3)$

Apply the famous CRT on $(1),(2),(3)$

Solution 2:

I was lazy to do the calculations required when applying the Chinese Remainder Theorem, so in the end I managed to come up with the following solution.

First note that $199$ is prime. By Fermat's Little Theorem we have, $$2^{198} \equiv 1\pmod{199} \implies 2^{199} \equiv2\pmod{199} \implies 2^{1990} \equiv 2^{10} \pmod{199}$$

$$ \implies\boxed{199\mid (2^{1990}-2^{10})}$$

We can also observe that $2^{1990}$ and $2^{10}$ have the same last digit, $4$, since $1990 \equiv 10 \equiv 2\pmod{4}$.

$$\implies\boxed{10 \mid (2^{1990}-2^{10})}$$

From the above we conclude that $$1990\mid (2^{1990}-2^{10}) \implies 2^{1990} \equiv 2^{10} \equiv 1024 \pmod{1990}$$

Therefore, the remainder when $2^{1990}$ is divided by $1990$ is $\boxed{1024}$