mathimatikoi.org

Find the five last digits of the number:

$$\mathscr{N}=\underbrace{9^{9^{9^{\cdot^{\cdot^{\cdot^{\cdot^{9}}}}} }}}_{1001 \;\; \rm {nines}}$$

I wonder which evil mind has concocted this exercise. Having solved it though, I will probably behave like Mike in this comic.

Tolis, please confirm if the answer is $45289$.

Edit: Added font colour on the hyperlink.

Demetres wrote: Tolis, please confirm if the answer is $45289$.

Affirmative.

As for the evil mind , no idea.

Ok then. Here we go.

Let me write $a_n$ for the tower of $n$ nines. In fact I will show that $a_n \equiv 45289 \bmod 100000$ for every $n \geqslant 5$.

Firstly, it is immediate that $a_n \equiv 9 \bmod 10$ for every $n \geqslant 1$. (Because $a_{n-1}$ is always odd.)

Modulo $100$ we have

\[ a_n \equiv (10-1)^{a_{n-1}} \equiv 10a_{n-1} - 1 \equiv 90-1 \equiv 89 \bmod 100\]

for every $n \geqslant 2$.

In the second congruence I have used the binomial expansion and omitted all terms which are multiples of $100$. We follow the same procedure with higher powers of $10$, but greater care is needed.

Modulo $1000$ we have

\[ a_n \equiv -100\frac{a_{n-1}(a_{n-1}-1)}{2} + 10a_{n-1} - 1.\]

Now, $a_{n-1} \equiv 9 \bmod 10$. Also, $(a_{n-1}-1) \equiv 88 \bmod 100$ so $(a_{n-1}-1)/2 \equiv 4 \bmod 10$. In more detail: $a_{n-1} = 100k+89$ for some integer $k$. Then $(a_{n-1}-1)/2 = 50k+44 \equiv 4 \bmod 10$.

This gives that $a_{n-1}(a_{n-1}-1)/2 \equiv 6 \bmod 10$. So overall we get

\[ a_n \equiv -600 + 890 - 1 \equiv 289 \bmod 1000\]

for every $n \geqslant 3$.

Modulo $10000$ we have

\[ a_n \equiv 1000\binom{a_{n-1}}{3} - 100\binom{a_{n-1}}{2} + 10a_{n-1} - 1\]

To compute $\dbinom{a_{n-1}}{3} \bmod 10$ we see that

\begin{align*}
\binom{a_{n-1}}{3} &= \frac{(1000k+289)(1000k+288)(1000k+287)}{6}\\
& = \frac{(1000k+289)(500k+144)(1000k+287)}{3} \\
&\equiv 7 \cdot 9 \cdot 4 \cdot 7\\
& \equiv 4 \bmod 4
\end{align*}
Here, the first $7$ appears because $7$ is the inverse of $3$ module $10$.

We also have to compute $\dbinom{a_{n-1}}{2} \bmod 100$ which with the same process gives $89 \cdot 44 \equiv 16 \bmod 100$. Overall we get

\[ a_n \equiv 4000 - 1600 + 2890 - 1 \equiv 5289 \bmod 1000\]

for every $n \geqslant 4$.

We have yet one more round to go:

\[ a_n \equiv -10000\binom{a_{n-1}}{4} + 1000\binom{a_{n-1}}{3} - 100\binom{a_{n-1}}{2} + 10a_{n-1} - 1\]

It is left as an exercise for the reader to check that $\dbinom{a_{n-1}}{4} \equiv 6 \bmod 10, \dbinom{a_{n-1}}{3} \equiv 64 \bmod 100$ and $\dbinom{a_{n-1}}{2} \equiv 116 \bmod 1000$. Putting all these together gives that the last 5 digits of $a_n$ are $45289$ for every $n \geqslant 5$.

I believe I now understand why the "evil" creator of this exercise went all the way up to 5 digits and he/she was not content with the last four digits.

In the solution, when we compute $\binom{m}{2} \bmod 10$ it is absolutely important to use the last two digits of $m$ and not just the last one. For example, if $m = 2$, then $\binom{m}{2} = 1 \equiv 1 \bmod 10$, while if $m = 12$, then $\binom{m}{2} = 66 \equiv 6 \bmod 10$.

So somebody might possibly get lucky and using the wrong method derive the right answer. When does this happen? Some fiddling around shows that if the digit he have omitted is even then we get the correct answer with the wrong procedure, while if the digit is odd then we do not.

The first instance in which we get an additional odd digit is when we have to use $5289$ rather than just $289$. To use $5289$, we need to ask for $5$ digits.