Large Numbers and Congruences

Date: 03/05/2002 at 12:42:43
From: Boris Dusek
Subject: Last three digits of large number

Find the last three digits of the number 11^(11^(11^(11^(11^11)))) 
written in base seven.

Date: 03/09/2002 at 06:57:06
From: Doctor Pete
Subject: Re: Last three digits of large number

Hi Boris,

This is a very challenging question! In order to answer it, I will 
have to use some ideas from elementary number theory; in particular, I 
assume you are already familiar with congruences. I will write

     a == b (mod m)

to mean a is congruent to b, modulo m.  Now, let

     P[0] = 1,
     P[n] = 11^P[n-1],

for all positive integers n.  Then

     11^(11^(11^(11^(11^11)))) = P[6].

The last three digits of P[6] in base 7 is equivalent to finding 
0 <= x < 343 such that

     P[6] == x (mod 343).

(Note 343 = 7^3.) This is because P[6] in base 7 has the 
representation

     P[6] = a[0]7^0 + a[1]7^1 + a[2]7^2 + ... + a[d]7^d,

where the coefficients a[0], a[1], ..., a[d] are nonnegative integers 
from 0 to 6. Thus, when P[6] is divided by 7^3, the remainder is

     x = a[0]7^0 + a[1]7^1 + a[2]7^2,

and we see that expressing x in base 7 will give us the last three 
base-7 digits of P[6].

That said, the first observation to make is that

     11^147 == 1 (mod 343).

How did I find this congruence? I used a computer. However, I used it 
for convenience, not out of necessity. This is because, if necessary, 
we can compute by hand

     11^2 == 121 (mod 343),
     11^4 == 121^2 == 235 (mod 343),
     11^8 == 235^2 == 2 (mod 343),
     11^16 == 2^2 == 4 (mod 343),
     11^32 == 4^2 == 16 (mod 343),
     11^64 == 16^2 == 256 (mod 343),
     11^128 == 256^2 == 23 (mod 343),
     11^147 = 11^(128+16+2+1) == 23*4*121*11 = 122452 == 1 (mod 343).

So, we have, for nonnegative integers k, m, with m < 147,

     11^(147k + m) = (11^147)^k * 11^m == 1^k 11^m = 11^m (mod 343).

It follows that we seek the the value of m for which P[5] = 147k + m, 
or equivalently, the remainder of P[5] divided by 147, or

     P[5] == m (mod 147).

To do this, we again compute successive powers of 11 modulo 147, and 
we find

     11^42 == 1 (mod 147),
and
     11^(42k' + m') = 11^m' (mod 147),

where 0 <= m' < 42, and 0 <= k'.  Thus by similar reasoning as before, 
we want to find m' such that

     P[4] == m' (mod 42).

By now the process should be clear; we compute

     11^6 == 1 (mod 42),

so we want to find a number m" such that

     P[3] == m" (mod 6).

This leads us to compute

     11^2 == 1 (mod 6),

so we want to find a number m"' such that

     P[2] = 11^11 == m"' (mod 2).

But since 11 is odd, 11^11 is itself odd, so m"' = 1. Therefore,

     P[3] == 11^m"' = 11^1 = 11 == 5 (mod 6),

hence m" = 5, and continuing back up along the chain of congruences we 
have constructed, we find

     P[4] = 11^m" = 11^5 == 23 = m' (mod 42),
     P[5] == 11^m' = 11^23 == 23 = m (mod 147),
     P[6] == 11^m = 11^23 == 219 (mod 343).

Thus x = 219, which, when written in base 7, is 432, since

     4*7^2 + 3*7 + 2 = 4*49 + 21 + 2 = 196 + 23 = 219,

so 4, 3, 2 are the last three digits of P[6] written in base 7.

I hope my explanation has been sufficiently clear. I used several 
important properties of congruences, so if you are unfamiliar with 
them, I highly suggest any book on elementary number theory.

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

Date: 03/10/2002 at 08:56:34
From: Boris Dusek
Subject: Last three digits of large number

Thank you for your answer. It was not only clear but also very 
challenging because you showed me the way(s) how you can sort out such 
difficult problems. So thank you very much for your response!