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 
to talk about this more.

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

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

Hi Vladimir,

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/