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

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

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!
```
Associated Topics:
High School 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