Math Forum Article on Modular Residues of Power Towers
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 NumberI'm not sure how to solve this, or even how to begin. Here goes.
Consider the recursive function f(n)=13f(n-1), where f(0)=1313.
So A = 1313, B = 13(1313), 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 = 1313 but it cannot compute y = 13x. 13x is just too large.
The key here is that we don't need to compute 13x - we just need to compute the last 8 digits of 13x. 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 22 — how would you do that? One way would be to divide 22 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(22) = 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(22)] = 216 = 65536 ?
So the answer is six. But could we have gotten that without directly computing 216?
We want to compute 216 mod 10. That is, we want to know:
216 = __ mod 10
The first way is to manually compute 216 mod 10, but that's hard if the number is large. The easier way is as follows:
Notice that 216 = (24)4
but 24 = 6 mod 10 so we can write:
216 mod 10 = (24)4 mod 10 = 64 mod 10 = (62)2 mod 10 = 362 mod 10
but 36 = 6 mod 10 so we can write
362 mod 10 = 62 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 1313 mod 108 and then take the answer we get (call it x), and compute: 13x mod 108
Of course, 13x will be too large to compute (even though x will be significantly smaller than 1313 - recall that x is only the last 8 digits of 1313) 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; 55045053I 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 2024 Aug 05.
s.27