Math Forum Article on "The Last Digits of Z"
URL: http://mathforum.org/library/drmath/view/51625.html Date: 20050306Last Eight Digits of Z
Date: 01/18/2002 at 01:00:42 From: Perry Alain Subject: Residue of Ridiculously Large Number I'm not sure how to solve this, or even how to begin. Here goes. Consider the recursive function f(n)=13^(f(n-1)), where f(0)=13^13. So A = 13^13, B = 13^(13^13), etc. A = f(0), B = f(A), C = f(B),... Z = f(Y). What are the last 8 digits of Z? ---------------------------------------------------------------------- Date: 01/18/2002 at 13:27:53 From: Doctor Paul Subject: Re: Residue of Ridiculously Large Number The answer is 55045053, but I'm not quite sure how to explain it to you. Obviously, I used a computer to get the answer. The program I used (Maple) can compute x = 13^13 but it cannot compute y = 13^x. 13^x is just too large. The key here is that we don't need to compute 13^x - we just need to compute the last 8 digits of 13^x. And there's a trick that will make this possible. Let me try to explain: Let's answer a simpler question for a moment. What if we wanted to compute the last digit of 2^2. How would you do that? One way would be to divide 2^2 by ten and see what the remainder was. That remainder will be 4 (which is the answer). Now what if you wanted the last digit of 2^(2^2) = 16? Divide 16 by 10. It goes 1 time with a remainder of six. This idea of computing remainders is very powerful and is usually referred to as the modulus operator (abbreviated "mod"). So we would write: 16 = 6 mod 10 This is just another way of saying that 16 is 6 more than a multiple of 10 or equivalently, that when 16 is divided by 10, the remainder is 6. What if you wanted the last digit of 2^[2^(2^2)] = 2^16 = 65536 ? So the answer is six. But could we have gotten that without directly computing 2^16? We want to compute 2^16 mod 10. That is, we want to know: 2^16 = ____ mod 10 The first way is to manually compute 2^16 mod 10, but that's hard if the number is large. The easier way is as follows: Notice that 2^16 = (2^4)^4 but 2^4 = 6 mod 10 so we can write: 2^16 mod 10 = (2^4)^4 mod 10 = 6^4 mod 10 = (6^2)^2 mod 10 = 36^2 mod 10 but 36 = 6 mod 10 so we can write 36^2 mod 10 = 6^2 mod 10 = 36 mod 10 = 6. This idea of exponentiating a little bit, then reducing mod 10, then exponentiating a bit more, then reducing mod 10, etc... is called modular exponentiation. The only way to solve your problem is to use a computer and to force the computer to do this modular exponentiation. We're looking for the last 8 digits so we will reduce 13^13 mod 10^8 and then take the answer we get (call it x), and compute: 13^x mod 10^8 Of course, 13^x will be too large to compute (even though x will be significantly smaller than 13^13 - recall that x is only the last 8 digits of 13^13) unless we force the computer to do the exponentiation modularly. In Maple, the % sign refers to the previous answer and the way to force Maple to do modular exponentiation is by using &^ to indicate exponentiation instead of the usual ^ key. Here's what I did in Maple: > 13^13; 302875106592253 > 13 &^ % mod 10^8; 88549053 > 13 &^ % mod 10^8; 44325053 > 13 &^ % mod 10^8; 84645053 > 13 &^ % mod 10^8; 27045053 > 13 &^ % mod 10^8; 95045053 > 13 &^ % mod 10^8; 55045053 > 13 &^ % mod 10^8; 55045053 > 13 &^ % mod 10^8; 55045053 > 13 &^ % mod 10^8; 55045053 I hope you see the pattern developing. Please write back if you'd like to talk about this more. - Doctor Paul, The Math Forum http://mathforum.org/dr.math/This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2021 Jul 19.
s.27