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

Question

I actually do not have the basic idea on how to approach these type of questions....so please tell me a generalized method about all this too.

It came in RMO, and the question is:

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

Answer 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)$

Answer 2

As the $(2^{1990},1990)=2$

let us start with $\displaystyle\frac{2^{1990}}2\pmod {\frac{1990}2}$ i.e., $2^{1989}\pmod {995}$

Now $\displaystyle995=5\cdot 199$ and using Carmichael function, $\lambda(995)=396$

As $\displaystyle(2,995)=1, 2^{396}\equiv1\pmod{995}$

As $\displaystyle1989\equiv9\pmod{396},2^{1989}\equiv2^9\pmod{995}$

$\displaystyle\implies2^{1989}\equiv512\pmod{995}\ \ \ \ (1)$

Now we know if $x\equiv y\pmod m, a\cdot x\equiv a\cdot y\pmod {a\cdot m}$ where $a$ is any integer

So, multiply either sides of $(1)$ by $2$

Answer 3

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}$