Carmichael's Theorem, Lambda FunctionDate: 06/11/2003 at 07:19:53 From: Rahul Radhakrishnan Subject: Figuring out the last 8 digits of 9^9^9^9 Dear Dr. Math, I saw in a magazine that using simple arithmetic properties one could find the last 8 digits of 9^9^9^9. Could you please tell me how? Thank you, Rahul Radhakrishnan. Date: 06/11/2003 at 09:49:39 From: Doctor Rob Subject: Re: Figuring out the last 8 digits of 9^9^9^9 Thanks for writing to Ask Dr. Math, Rahul. You want 9^(9^[9^9]) (mod 10^8). We can use the following theorem of Robert Carmichael to help: If a and m are relatively prime, then a^(lambda[m]) = 1 (mod m), where lambda(x) is the Carmichael lambda-function. Since 9 and 10^8 are relatively prime, and lambda(10^8) = LCM[lambda(2^8),lambda(5^8)], = LCM[2^6,4*5^7], = 2^6*5^7, that tells us that 9^(5000000) = 1 (mod 10^8). That means we need to find 9^(9^9) (mod 5000000). Applying Carmichael's Theorem again, we find that lambda(5000000) = LCM[2^4,4*5^6] = 2^4*5^6 = 250000, 9^(250000) = 1 (mod 5000000), so we need to find 9^9 (mod 250000). This we can do with a calculator. 9^9 = 387420489, and, reducing modulo 250000, one finds the result 170489. Thus we can build up to the answer by finding 9^170489 = a (mod 5000000), 9^a = b (mod 10^8), and b is your answer. I leave it to you to see why the above will give you the right answer, and to see how to calculate a and b in the last two equations above. Feel free to write again if I can help further. - Doctor Rob, The Math Forum http://mathforum.org/dr.math/ Date: 06/16/2003 at 08:02:08 From: Rahul Radhakrishnan Subject: Figuring out the last 8 digits of 9^9^9^9 Dear Dr. Rob, I had never heard of Robert Carmichael's theorem. Now I understand it, but what is Carmichael's lambda function? Second, you said that 9^170489 = a mod(50,00,000). How do I evaluate a? Using logarithms will not give the exact answer. Thank you for your reply, Rahul Radhakrishnan Date: 06/16/2003 at 09:55:23 From: Doctor Rob Subject: Re: Figuring out the last 8 digits of 9^9^9^9 Thanks for writing back to Ask Dr. Math, Rahul. Carmichael's lambda function can be computed as follows: lambda(2) = 1, lambda(2^2) = 2, lambda(2^e) = 2^(e-2) for e > 2, lambda(p^e) = (p-1)*p^(e-1) for p > 2 and prime, lambda(p[1]^e[1]*...*p[r]^e[r]) = LCM[lambda(p[1]^e[1]),...,lambda(p[r]^e[r])], all p[i]'s prime. lambda(n) is the smallest exponent such that x^lambda(n) = 1 (mod n) for all x relatively prime to n. In your case, you need only the following formula, which follows from the above definition: lambda(2^e*5^f) = 2^(e-2)*5^(f-1), e > 3. To evaluate 9^170489 = a (mod 5000000), you can compute in order 9^2 = 81 (mod 5000000) 9^4 = (9^2)^2 = 81^2 = 6561 (mod 5000000) 9^5 = (9^4)*9 = 6561*9 = 59049 (mod 5000000) 9^10 = (9^5)^2 = 59049^2 = 1784401 (mod 5000000) 9^20 = (9^10)^2 = 1784401^2 = 1928801 (mod 5000000) 9^40 = (9^20)^2 = 1928801^2 = ... 9^41 = 9^40*9 = ... 9^82 = (9^41)^2 = ... 9^83 = ... 9^166 = ... 9^332 = ... 9^664 = ... 9^665 = ... 9^1330 = ... 9^1331 = ... 9^2662 = ... 9^2663 = ... 9^5326 = ... 9^5327 = ... 9^10654 = ... 9^10655 = ... 9^21310 = ... 9^21311 = ... 9^42622 = ... 9^85244 = ... 9^170488 = ... 9^170489 = ... = a (mod 5000000). At each step, you are either doubling the exponent (by squaring) or adding one to it (by multiplying by 9). This is related to the binary expansion of 170489. You can keep all the numbers relatively small by reducing modulo 5000000 after each step. A similar chain can be constructed to compute b = 9^a (mod 10^8). Feel free to write again if I can help further. - Doctor Rob, 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/