Five last digits of number

Number theory
Post Reply
User avatar
Tolaso J Kos
Administrator
Administrator
Posts: 867
Joined: Sat Nov 07, 2015 6:12 pm
Location: Larisa
Contact:

Five last digits of number

#1

Post by Tolaso J Kos »

Find the five last digits of the number:

$$\mathscr{N}=\underbrace{9^{9^{9^{\cdot^{\cdot^{\cdot^{\cdot^{9}}}}} }}}_{1001 \;\; \rm {nines}}$$
Imagination is much more important than knowledge.
Demetres
Former Team Member
Former Team Member
Posts: 77
Joined: Mon Nov 09, 2015 11:52 am
Location: Limassol/Pyla Cyprus
Contact:

Re: Five last digits of number

#2

Post by Demetres »

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.
Last edited by Demetres on Tue Nov 10, 2015 6:35 pm, edited 1 time in total.
User avatar
Tolaso J Kos
Administrator
Administrator
Posts: 867
Joined: Sat Nov 07, 2015 6:12 pm
Location: Larisa
Contact:

Re: Five last digits of number

#3

Post by Tolaso J Kos »

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

As for the evil mind , no idea.
Imagination is much more important than knowledge.
Demetres
Former Team Member
Former Team Member
Posts: 77
Joined: Mon Nov 09, 2015 11:52 am
Location: Limassol/Pyla Cyprus
Contact:

Re: Five last digits of number

#4

Post by Demetres »

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 :evil: 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$.
Demetres
Former Team Member
Former Team Member
Posts: 77
Joined: Mon Nov 09, 2015 11:52 am
Location: Limassol/Pyla Cyprus
Contact:

Re: Five last digits of number

#5

Post by Demetres »

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.
Post Reply

Create an account or sign in to join the discussion

You need to be a member in order to post a reply

Create an account

Not a member? register to join our community
Members can start their own topics & subscribe to topics
It’s free and only takes a minute

Register

Sign in

Who is online

Users browsing this forum: No registered users and 5 guests