Last Eight Digits of ZDate: 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/ Date: 03/26/2005 at 17:50:25 From: Vladimir Subject: modular exponentiation An interesting pattern was pointed out in the reponse to this question. I am interested in the proof of this pattern. Define f by f(0)=13 and f(n)=13^(f(n-1)). Is there a proof that f(n) is congruent to f(n+1) mod 10^n? For example, f(0)=13 is congruent to f(1)=13^13=302875106592253 mod 10^0=1 and f(1)=302875106592253 is congruent to f(2) mod 10^1=10. I've tested the pattern with various bases other than 13 and it has held for all the primes I've used to test it. I've tried an inductive proof, but i didn't get very far. I defined the function in Mathematica by f[n_] := PowerMod[13, f[n - 1], 10000000000]; f [1] := 13 and I generated a table of the values using Do[Print[f [n]], {n, 14}] so that I could observe the pattern. I've considered using Euler's Theorem, but I didn't get very far using that either. Your help would be most appreciated. Date: 03/27/2005 at 04:54:31 From: Doctor Jacques Subject: Re: modular exponentiation Hi Vladimir, Euler's theorem is indeed the right idea, but we need to improve it a little. Euler's theorem says that, if gcd(x,n) = 1, then x^phi(n) = 1 (mod n) However, this is not always the best possible result: phi(n) is not always the smallest integer k such that x^k = 1 (mod n) for all x relatively prime with n. Assume that n = a*b, with gcd (a,b) = 1; we have phi(n) = phi(a)*phi(b). Let us define: L(n) = lcm (phi(a), phi(b)) Now, if gcd(x,n) = 1, we have: x^L(n) = 1 (mod a) [1] because x^phi(a) = 1 and phi(a) divides L(n). In the same way, we have: x^L(n) = 1 (mod b) [2] Taken together, [1] and [2] imply: x^L(n) = 1 (mod n) [3] by the Chinese Remainder theorem. Note that L(n) divides phi(n), and this shows that Euler's theorem is a consequence of [3]. If a and b are greater than 2, phi(a) and phi(b) will both be even, and they will at least have a factor 2 in common. This shows that, in this case, L(n) will be strictly less than phi(n) - we have a stronger result than Euler's theorem. Let us now look at L(10^n) = L((2^n)*(5^n)). We have: phi(2^n) = 2^(n-1) phi(5^n) = 4*5^(n-1) If n >= 3, 2^(n-1) is a multiple of 4, and we have: L(10^n) = 2^(n-1)*5^(n-1) = 10^(n-1) [4] If n < 3, we compute directly: L(10^1) = lcm(1,4) = 4 [5] L(10^2) = lcm(2,20) = 20 [6] (Note that L(10) = phi(10), and L(100) < phi(100) = 40). After these preliminaries, let us return to the problem at hand. We will assume that p is a prime different from 2 and 5 (in fact, it is sufficient to assume that gcd(p,10) = 1). Given f(0) = p f(n+1) = p^f(n) we want to prove that f(n+1) = f(n) (mod 10^n) As the sequence is defined recursively, it is natural to try to prove this by induction. As the general formula [4] is only valid for n >= 3, we will handle the cases n = 1 and 2 separately. Assume first that n >= 3. The induction hypothesis is: f(n) = f(n-1) (mod 10^(n-1)) Because of [4], we can write this as: f(n) = f(n-1) (mod L(10^n)) f(n) = f(n-1) + k*L(10^n) [7] for some integer k. We can write: f(n+1) = p^f(n) = p^(f(n-1) + k*L(10^n)) = p^f(n-1) * p^(k*L(10^n)) = f(n) * p^(k*L(10^n)) and, because of [3], we have p^(L(10^n)) = 1 (mod 10^n) and this yields: f(n+1) = f(n) (mod 10^n) which is what we wanted to prove. We still have to consider the cases n = 1 and 2. For n = 1, note that p^2 = 1 (mod 4) for any odd number p, and this implies that: f(1) = p^p = p*p^(p-1) = p = f(0) (mod 4) because p-1 is even. As L(10) = 4, we can use exactly the same argument as above to show that: f(2) = f(1) (mod 10^1) [8] In fact, we can prove a little more. If we write: f(1) = f(0) + 4k we have, as before: f(2) = f(1) * p^(4k) and, as p^2 = 1 (mod 4), we have: f(2) = f(1) (mod 4) [9] and, [8] and [9] imply that: f(2) = f(1) (mod 20) Now, L(10^2) = 20, and the same argument gives: f(3) = f(2) (mod 10^2) and this completes the missing steps in our induction proof. Note that we assumed that gcd(p, 10) = 1. For p = 2, the theorem is not true, as the sequence is: 2, 4, 16, 256, ... (in this case, we have f(n+1) = f(n) (mod 10^(n-1)) instead). For p = 5, the theorem is true, but the above proof is not valid - the theorem can be proved by considering separately the congruences mod 2^n and mod 5^n. The genral idea is to note that, mod 5^n, the congruence holds because the exponent of 5 is much larger than needed, and, mod 2^n, we have L(2^n) = 2^(n-2). Does this help? Write back if you'd like to talk about this some more, or if you have any other questions. - Doctor Jacques, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/