Associated Topics || Dr. Math Home || Search Dr. Math

### Carmichael's Theorem, Lambda Function

```Date: 06/11/2003 at 07:19:53
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,
```

```
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

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
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.

```

```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search