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/