# What is the last digit of 3^100?

1. May 8, 2007

### smithg86

1. The problem statement, all variables and given/known data

What is the last digit of 3^100?

2. Relevant equations

This was a question on my practice final. There are no relevant formulas, but I think modular arithmetic is involved. (?)

3. The attempt at a solution

I have no idea where to start.

2. May 8, 2007

### AKG

What's 3100 mod 10?

3. May 8, 2007

### Staff: Mentor

Hint: what is 100/4? Is it an even number? What is 3^0 ?

Okay, enough hints.

(one last hint -- after you get your paper answer, just use Excel to check your answer, using Ctrl-D to paste your numbers and equations down to make it a quick check)

4. May 8, 2007

### smithg86

3^(n+4) (is congruent to) 3^n, mod 10.
Also, 100/4 = 25 + 0, so
3^100 (is congruent to) 3^0=1, mod 10.
So the last digit is 1.

5. May 8, 2007

### Staff: Mentor

Oopsies -- Excel still works, but you have to do something manually. Otherwise the large numbers involved require floating point math and exponential notation. Whatever.

6. May 8, 2007

### smithg86

i used my ti-89 calculator to verify the answer. thanks.

7. May 8, 2007

### Staff: Mentor

Correct-amundo.

8. May 8, 2007

Show-off

9. May 8, 2007

### matt grime

That wouldn't have been my response. Mine is 'put the bloody calculator away'.

10. May 8, 2007

### Staff: Mentor

Yeah, but he'd done the work already and was just checking his work with the calculator. I do that all the time to try to avoid making errors. Now if he'd just used the calcy in the first place, I agree with you.

11. May 8, 2007

### matt grime

But who cares? So what if you made a numerical error - the method is what is important. If, on an exam, you wrote you were about to use FLT, or just group theory, that states BLAH and had the correct method but made some dumb numerical error then I WOULD NOT CARE, and deduct at most 1 mark. And, of course, in an exam, you shouldn't be allowed a calculator. Get things in perspective. What is important is, perversely, not the last digit of 3^100, but that you're using FLT.

12. May 8, 2007

### Staff: Mentor

Well, NASA probably cared that they missed an error when they missed Mars (how many times? I forget.). My point was that it is good practice (at least in Engineering) to check your answers with a different method. Mistakes are costly in many ways.

And I thought the OP did the problem and check in the proper way -- did the work by hand first, and then cross-checked the answer with a PC or calculator. That's typically how I do it in my every-day work as an MSEE in our R&D Lab.

I do agree that on many exams where calculators are not allowed, etc., that making a small numerical error should not cost many points. The purpose of that is to reward the effort that went into learning the material. But once the material is learned, the application of that learning in the real world absolutely has to be cross-checked in other ways in order to avoid costly mistakes, IMO.

13. May 8, 2007

### matt grime

And would NASA have bothered working it out by hand first? This is a nonsensical defence. (....and the mathematician, upon satisfying himself there were equations that could be solved went back to bed. The Engineer, Physicist, Mathematician fire in the waste paper basket gag. Actually, I prefer the '... and the mathematician upon waking, saw his candle was still alight. He put it in the wastepaper basket, thus reducing it to a previously known case, and went back to bed' ending.)

Last edited: May 8, 2007
14. May 8, 2007

### Staff: Mentor

I don't know, to be honest. I'm relatively sure that the mission(s) planning started on a white board somewhere. My point was that it is good practice to cross-check your answers with a different technique. And as long as the OP used the technique that he was supposed to in order to work out the initial answer (using the math techniques of the subject he is learning), then the method of the cross-check is up to him.

Even when I'm adding a column of numbers by hand, I will always go back and at least add them up again bottom-to-top. And in financial spreadsheets, it's good practice to have the row and column sub-totals added together for a cross-check. Not sure what that financial technique is called, though....

15. May 8, 2007

### matt grime

Nasa's mistake, on the Mars thing, wasn't a mistake of arithmetic - it was mixing up SI and imperial measurements, if I recall the debacle correctly (But see my edited post above). There were numerical errors in the patriot missiles coding that meant, in Gulf War I, that they didn't actually hit any Iraqi SCUDS, contrary to popular belief. Fortunately the SCUDS were so bad they didn't hit their intended targets anyway. Other popular anti-military anecdotes (and therefore coming with no guarantees of veracity) fed to us during one course were the tanks for the US that overheated and set fire to surrounding trees (engines without limiters), and the Navy who thought dumping overboard was acceptable because, in their 'instant perfect mixing model', there were no concentrations of pollutants. That was a fun lecturer. I think he was slightly political.

Last edited: May 8, 2007
16. May 8, 2007

### chroot

Staff Emeritus
There's no harm in using an alternate method to check your answer when the instructor does indeed deduct massive points for a wrong conclusion, despite a correct approach. It's very possible the OP has such an instructor, yet we don't really know. Any arguments about whether or not the OP should check his work are necessarily completely unfounded. (Does it really matter anyway? I'll give you the conclusion to this one: no.)

- Warren

17. May 8, 2007

### matt grime

But actually working out 3^100 is implying that the theory is wrong. And that is pointless. Indeed, since 3 has order 4, mod 10, and 3^100=(3^4)^25 mod 10, there is NO NEED to check the answer. It is nonsensical to suggest otherwise: unless you think you can't divide 100 by 4 and get the correct remainder. Now, if the question were about 26^193456567 mod some really big prime, that might be different. But in this case PUT THE CALCULATOR AWAY! Get some perspective on what is reasonable....

Last edited: May 8, 2007
18. May 8, 2007

### smithg86

i was only able to see that 3^(n+4) (is congruent to) 3^n, mod 10 by multiplying a few powers of 3 by hand and seeing a pattern. is there another method, other than seeing the pattern? what if the question was "what is the last digit of x^y, such that x and y are integers?"

19. May 8, 2007

### StatusX

First note that if a=a' (mod 10) and b=b' (mod 10), then ab=a'b' (mod 10). So it always suffices to look at the last digits, ie, the numbers 0,1,...,9.

Say you start with 2. Then the powers of 2 mod 10 are 2,4,8,6,2,4,8,6,..., and so on. Note that once you get back to the original number, the pattern must repeat. Similarly, you can work out the following:

0,0,...
1,1,...
2,4,8,6,2,...
3,9,7,1,3,...
4,6,4,...
5,5,...
6,6,...
7,9,3,1,7,...
8,4,2,6,8,...
9,1,9,...

So, for example, the last digit of the power of any number ending in an 8 only depends on the power mod 4, eg, 25438678676843342258^185876586585265 ends in an 8, since 65 = 1 (mod 4). And you can't use a calculator to verify that, so you'll have to trust the theory.

You could try to work out similar patterns for bases other than 10, and see if you get any patterns to the patterns. This kind of thing is the subject of group theory or ring theory.

Last edited: May 8, 2007
20. May 9, 2007

### matt grime

Just find the first instance of when x^r=1 mod 10, then take y mod r and work it out by hand. Of course, if x is not prime to 10 this will never happen, and if x is prime to 10 it must happen for r=1,2 or 4. You shuold try to prove that it must happen for 1<=r<=4, since that is straight-forward. Hint: apply the pigeon hole principle to x^1,x^2,x^3,x^4,x^5, noting that there are only 4 numbers between 1,..,10 that are prime to 10.

If you want to know why it can't be 3, then that is one of the first results you'll learn in group theory, called Lagrange's Theorem.