Question

What is the remainder obtained when 2¹⁹⁹⁰ is divided by 1990?

Answer 1

2^1990 mod 1990

1990 = 1024 + 512 + 256 + 128 + 64 + 4 + 2
1990 = 2^10 + 2^9 + 2^8 + 2^7 + 2^6 + 2^2 + 2^1

2^1990 mod 1990
= 2^(1024 + 512 + 256 + 128 + 64 + 4 + 2) mod 1990
= [ (2^1024 mod 1990) (2^512 mod 1990) (2^256 mod 1990) (2^128 mod 1990) (2^64 mod 1990) (2^4 mod 1990) (2^1 mod 1990) ] mod 1990

2^2 mod 1990 = 4
2^4 mod 1990 = 16
2^64 mod 1990 = 16^16 mod 1990 = 126
2^128 mod 1990 = 126^2 mod 1990 = 1946 mod 1990 = -44
2^256 mod 1990 = (-44)^2 mod 1990 = 1936 mod 1990 = -54
2^512 mod 1990 = (-54)^2 mod 1990 = 1946 mod 1990 = 926
2^1024 mod 1990 = 926^2 mod 1990 = 1776 mod 1990 = -214

Continue
= [ (2^1024 mod 1990) (2^512 mod 1990) (2^256 mod 1990) (2^128 mod 1990) (2^64 mod 1990) (2^4 mod 1990) (2^1 mod 1990) ] mod 1990
= [ (-214) (926) (-54) (-44) (126) (16) (4) ] mod 1990
= -3796834922496 mod 1990
= 1024