4
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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$.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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} $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.