Find the remainder when 2^1990 is divided by 1990?

Question

Show your solution also.

Answer is ok but I want the details of solution, especially the calculation of x(mod 1990).

Answer 1

2^1990≡a (mod 1990)

a≡2^1990≡0^1990≡0 (mod 2)
a≡2^1990≡4^995≡ (-1)^995=-1≡4 (mod 5)
a≡2^1990≡(2^10)^199 ≡2^10=1024≡29 (mod 199)

Using the above (a≡0 (mod 2) a≡4 (mod 5))
a≡4 (mod 10) I hope this is easy to see.

now using a≡4 (mod 10) and 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.
But
a≡5004≡ 1024 (mod 1990)

so the remainder is 1024

Answer 2

There's probably some Chinese remainder theorem answer for this, along the lines of the prime factorization of:
1990 is 2 * 5 * 199.
2^1990 mod 2 = 0.
2^1990 mod 5 = 4.
2^1990 mod 199 = whatever it is.

I grabbed an Excel spreadsheet.
Cell A1 = 2,
Cell A2 = MOD(2*A1,1990)
Copy Row 2 down to Row 1990.

I came up with 1024, too.

[Edited to comment]
Nice job, Eulercrosser!

Answer 3

1024.
Rem(2^1990,1990) = 2^1990 mod 1990
= 2^(50*20+33*30) mod 1990
= 2^(50*20) mod 1990 * 2^(33*30) mod 1990
= (2^20)^50 mod 1990 * (2^30)^33 mod 1990
We must find each term then multiply mod 1990.
2^20 mod 1990 = 1836
1836^2 mod 1990 = 1826
1826^5 mod 1990 = 1596
1596^5 mod 1990 = 626
For the second part:
2^33 mod 1990 = 92
92^30 mod 1990 = 92^5 mod 1990 * 92^6 mod 1990 = 1394
Therefore the remainder is (626*1394) mod 1990 = 1024

Answer 4

1024