Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Carmichael's Theorem, Lambda Function

Date: 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/ 
Associated Topics:
College Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/