To The Power 2000!

Number Theory Level 4

What is the remainder when $1991^{2000}$ is divided by $10^6$ ?

The answer is 880001.

1 solution

Karim Fawaz
Jul 10, 2016

$1991^{2000}$ Mod 1000000 =

$964081^{1000}$ Mod 1000000 =

$174561^{500}$ Mod 1000000 =

$524721^{250}$ Mod 1000000 =

$83841^{125}$ Mod 1000000 =

$(83841^{1}$ Mod 1000000) X $(83841^{4}$ Mod 1000000) X $(83841^{8}$ Mod 1000000) X $(83841^{16}$ Mod 1000000) X $(83841^{32}$ Mod 1000000) X $(83841^{64}$ Mod 1000000) Mod 1000000 =

(83841 X 984961 X 171521 X 453441 X 740481 X 111361) Mod 100000 = 880001

Answer = $\boxed{880001}$

Moderator note:

Iterative squaring is a good way to deal with these large exponentiations.

nice one..+1

Ayush G Rai - 4 years, 11 months ago

@Karim Fawaz

But how this much calculation is possible without calculator.

Please post it using theorems like CRT, Euler's phi function, Fermat theorem etc.

Priyanshu Mishra - 4 years, 9 months ago

To The Power 2000!

The answer is 880001.

1 solution

Moderator note:

0 pending reports