2014/108) Find the remainder when $2^{1990}$ is divided by 1990

We have 1990 = 10*199 = 2* 5* 199

now we have

$2^4$ mod 5 = 1 as per fermat theorem
so $2^{1990}$ mod 5 = $2^2$ mod 5 = 4 mod 5

$2^{ 198} = 1$ mod 199

so $2^{1990}$ mod $199$ = $2^10$ mod 199 = 1024 mod 199 = 29 mod 199

$2^{1990}$ mod 2 = 0

so $2^{ 1990}$ mod 199 = 29
$2^{1990}$ mod 5 = 4

using Chinese Remainder Theorem you can proceed

continuing further

$2^{1990} = 0$ mod 2
$2^{1990} = 4$ mod 5

this gives $2^{1990} = 4$ mod 10

now using
$a = 4 (mod\, 10)$
$a = 29 (mod\, 199)$

Notice that 20*10+(-1)*199=1, thus 20*10≡1 (mod 199) and -199≡1 (mod 10)

let a= 29*(20•10)+4*(-199), then it is clear that
a = 29*(0)+4*(1)=4 (mod 10) and a=29•(1)+4•(0)=29 (mod 199) so this a works for what we want.

a= 5004=1024 (mod 1990)

so the remainder is 1024