How to find the last two digits of 3^1000? [duplicate]

$\begingroup$

So I think the problem reduces to 3^1000 mod 100. So I used the Eulers Totient to find phi(100)= 40. Then 3^1000 = (3^40)^25 = 1 mod 100. Is something wrong?

$\endgroup$ 1

3 Answers

$\begingroup$

No, that looks entirely right.

In fact $3^{1000}$ is

 13220708 1948080663 6890455259 7521443659 6542203275 2148167664
9203682268 2859734670 4899540778 3138506080 6196390977 7696872582
3559509545 8210061891 1865342725 2579536740 2762022519 8320803878
0147742289 6484127439 0400117588 6180411289 4781562309 4438061566
1730540866 7449050617 8125480344 4055470543 9703889581 7465368254
9161362208 3026856377 8582290228 4163983078 8789691855 6404084898
9376093732 4217184635 9938695516 7650189405 8810906042 6089671438
8641028143 5038564874 7165832010 6143661321 7310276890 2855220001

$\endgroup$ $\begingroup$

The answer is right "also" because the last two digits of $3^n$ are the same as those of $3^{n+20}$, so you're looking for the last two digits of $3^0$.

$\endgroup$ 3 $\begingroup$

You are absolutely right. Since $\varphi(100)=40$ we have $3^{1000}\equiv(3^{\phi(1000)})^{25}\equiv1^{25}\equiv 1 \bmod 100$ by Euler's theorem.

$\endgroup$ 2