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$ ?
chinese remainder theorem
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$ ?
Best Answer
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)$