Saturday, June 16, 2012

... is 3

Yesterday's puzzle was "What is the last digit of 3^2153?"  Today I'll show a technique for answering the question.

The simplest approach is to simply get out the calculator and type in 3^2153 and see what the last digit is. Unfortunately, my calculator isn't powerful enough to answer that question, giving me the screenshot off to the side. The reason for this is that my calculator, (which is the same TI 83 or TI 84 that most of my students have access to) is only capable of working with numbers that have less than 100 digits. Worse, it will only display approximately 10 of those digits (though there are tricks you can use to display a few more!).

Just how many digits does this number have anyway?  When asking that question, the tool to use is the log function. Typing log(3^2153) would hypothetically give you the answer (you'll have to round up to the nearest whole number) but even that is impossibly big for the calculator. I can use a property of logarithms to rewrite it as 2153* log (3) which is calculable:  $log_{10}(3^{2153})=2153 \cdot log_{10}(3) \approx 1027.24$. Practically, this means that the number 3*2153 has 1028 digits in it, and I'm interested in just the last one.  Interestingly, this subquestion of how many digits a huge number has been able to be answered for far longer than we have had calculators, by using log tables, but that's an entirely different story.

Back to the question at hand.  If we aren't going to just cheat and look at all the digits of a supercalculator, how can we answer the question?  Someone always suggests just multiplying it out by hand. As ridiculous as that would be (simply multiplying the last step would probably take 5 minutes, and that's after getting there in the first place!) the approach actually reveals something very important that can apply, so lets try it.
The numbers are already getting pretty big, but the final digit of each is all that's important to this discussion, and if you pay attention, you'll notice that there is a definite pattern to those digits. The last digits are 3, 9, 77, 1, 3, 9, 7, 1, and so on. This pattern will continue up long past the ability of our calculators (or pencils and papers) to handle, and all that is necessary to answer the question is where in this sequence of numbers 3^2153 falls.

Notice, this cycle of numbers repeats every four digits. Specifically, every multiple of four (3^4, 3^8, and 3^12) ends in a 1.  The closest power of four to 2153 is 2152, and so:
And so we have it -- 3^2153 ends in a 3.

I encourage you to try to answer the rest of these questions, which can all be answered using similar techniques:
Last digit of 2^2153
Last digit of 4^2153
Last digit of 5^2153
Last digit of 6^2153
Last digit of 7^2153
Last digit of 8^2153
Last digit of 9^2153