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

### Last Eight Digits of Z

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

- Doctor Paul, The Math Forum
http://mathforum.org/dr.math/
```

```
Date: 03/26/2005 at 17:50:25
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

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