Solving for the last two digits of a large number $3^{1000}$?

I found this question asking to find the last two digits of $3^{1000}$ in my professors old notes and review guides.

What material must I know to solve problems like this with remainders.I know Wilson's Theorem and there is mention on this packet of Euler's Theorem. Would I look into that to be able to solve problems like this? Why can we solve problems like this.

In summary, I decided to look a little bit ahead and in the meantime cool tips and pointers would be great for this area of 'future material type' that will be covered.

• Can't you just start multiplying and see if the last two digits will follow some kind of repeated cycle? – Bram28 Oct 28 '17 at 1:33
• You need Fermat,s little theorem. – Thomas Andrews Oct 28 '17 at 1:33
• Are you sure that I can use Fermat's Little Theorem? Could I use Euler's here as well? – R.ron Oct 28 '17 at 1:50
• – lab bhattacharjee Oct 28 '17 at 2:34
• best! links appreciated! – R.ron Oct 28 '17 at 3:22

There is almost certainly a better way, but off the top of my head this is how I would do it. Finding the last two digits of $3^{1000}$ is equivalent to computing $3^{1000}\mod100$. As $3^5=243$ we have that $3^5=43\mod100$. You can similarly check that $43^2=49\mod100$, and then $49^2=1\mod100$. Therefore, we have that $3^{20}=1\mod100$. By raising both sides to the power of $50$, we conclude that $3^{1000}=1\mod100$, i.e. the last two digits of $3^{1000}$ are $01$.

I'd just start multiplying and see what happens to the last two digits; they're certain to cycle around at some point:

3,9,27,81,43,29,87,61,83,49,47,41,23,69,07,21,63,89,67,01,03,09,27,...

Yes, there it is ... and we see it cycles with a cycle length of 20, and since the 20th is 01, the 1000th will be 01 as well.

But of course that's a pretty dumb method ... I don't know any more advanced method.

Using Euler function you will get phi(100)= 40

                   3^40 = 1 (mod 100).


Since 1000 = 40 x 25... from there, you can draw your own conclusion.

One could apply the binomial theorem here: $$3^{1000} = 9^{500} = (10-1)^{500} = \sum_{k=0}^{500} {500 \choose k}10^k (-1)^{500-k}$$ The third equality follows from the binomial theorem. All powers of $10^k$ modulo $100$ vanish when $k >= 2$. So, only the first two terms of the sum remain: $$3^{1000} \pmod {100} \equiv (10^0 (-1)^{500} + 10^1 (-1)^{499} \ 500) \pmod {100} \equiv 1 \pmod {100}$$