It is currently Wed Jan 16, 2019 9:54 pm

 All times are UTC [ DST ]

 Page 1 of 1 [ 5 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: Five last digits of numberPosted: Tue Nov 10, 2015 3:59 pm

Joined: Sat Nov 07, 2015 6:12 pm
Posts: 838
Location: Larisa
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.

Top

 Post subject: Re: Five last digits of numberPosted: Tue Nov 10, 2015 5:53 pm

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

Last edited by Demetres on Tue Nov 10, 2015 6:35 pm, edited 1 time in total.

Top

 Post subject: Re: Five last digits of numberPosted: Tue Nov 10, 2015 5:58 pm

Joined: Sat Nov 07, 2015 6:12 pm
Posts: 838
Location: Larisa
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.

Top

 Post subject: Re: Five last digits of numberPosted: Wed Nov 11, 2015 2:21 pm

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

Top

 Post subject: Re: Five last digits of numberPosted: Wed Nov 11, 2015 2:40 pm

Joined: Mon Nov 09, 2015 11:52 am
Posts: 77
Location: Limassol/Pyla Cyprus
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.

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 5 posts ]

 All times are UTC [ DST ]

#### Mathimatikoi Online

Users browsing this forum: No registered users and 0 guests

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

Search for:
 Jump to:  Select a forum ------------------ Algebra    Linear Algebra    Algebraic Structures    Homological Algebra Analysis    Real Analysis    Complex Analysis    Calculus    Multivariate Calculus    Functional Analysis    Measure and Integration Theory Geometry    Euclidean Geometry    Analytic Geometry    Projective Geometry, Solid Geometry    Differential Geometry Topology    General Topology    Algebraic Topology Category theory Algebraic Geometry Number theory Differential Equations    ODE    PDE Probability & Statistics Combinatorics General Mathematics Foundation Competitions Archives LaTeX    LaTeX & Mathjax    LaTeX code testings Meta