10
$\begingroup$

I was doing some basic Number Theory problems and came across this problem and was all thumbs :

Find the last three digits of $9^{9^{9^9}}$

How would I go about solving this problem? I am a newbie.

$\endgroup$
  • 1
    $\begingroup$ I edited your post. Please verify that this is what you intended. $\endgroup$ – Cameron Williams Feb 16 '15 at 3:21
  • $\begingroup$ Yes , @CameronWilliams , thanks - I was already going to do this edit ... $\endgroup$ – pranav Feb 16 '15 at 3:22
  • $\begingroup$ This question is an instantiation of this one math.stackexchange.com/questions/166083/… $\endgroup$ – thang Feb 16 '15 at 5:15
4
$\begingroup$

$(10-1)^{9^{9^9}}=\sum\limits_{i=0}^{9^{9^9}}\binom{9^{9^9}}{i}10^i(-1)^{9^{9^9}-i}$ of course we only care when $i$ is $0,1$ or $2$. So we need only calculate

$(-1)^{9^{9^9}}+\binom{9^{9^9}}{1}10^1(-1)^{9^{9^9}-1}+\binom{9^{9^9}}{2}10^2(-1)^{9^{9^9}-2}=-1+\color{red}{\binom{9^{9^9}}{1}10}-\color{green}{100\binom{9^{9^9}}{2}}$.

So we need only determine the last two digits of $9^{9^9}$ and the last digit of $\binom{9^{9^9}}{2}$ to conclude.

We first calculate the last digit of $\binom{9^{9^9}}{2}=\frac{9^{9^9}}{1}\frac{9^{9^9}-1}{2}$. The last digit of $9^{9^9}$ is $9$. So the last digit of $9^{9^9}-1$ is $8$. The last digit of $\frac{9^{9^9}-1}{2}$ is $4$ because $9^{9^9}-1$ is a multiple of $4$ since $9\equiv 1\bmod 4$.

Therefore the last digit of $\binom{9^{9^9}}{2}$ is $\color{green}6$.

What are the last two digits of $9^{9^9}$? We use the same trick as before, we want $(10-1)^{9^9}=\sum\limits_{i=0}^{9^9}\binom{9^9}{i}10^i(-1)^{9^9-i}$. But we only care about the first two terms:

$(-1)^{9^9}+\binom{9^9}{1 }10^1(-1)^{9^9-1}=10(9^9)-1$ which ends in $\color{red}{89}$.

Therefore $9^{9^{9^9}}$ is $-1+\color{red}{89(10)}-\color{green}{600}+1000k$

and hence ends in $289$.

$\endgroup$
  • 1
    $\begingroup$ You can delete wrong answers while you edit them, to keep people from wasting their time reading them, going "that's wrong," only to find your comment noting you know it is wrong $\endgroup$ – Thomas Andrews Feb 16 '15 at 3:32
  • $\begingroup$ @ThomasAndrews I'm sorry, can we pretend it didn't happen? $\endgroup$ – Jorge Fernández Hidalgo Feb 16 '15 at 4:20
  • $\begingroup$ he was snarky in response to my original comment (which I think is a polite reminder of basic etiquette here.) @CameronWilliams So it was called for. He has since deleted his comments. Not sure if you saw them. $\endgroup$ – Thomas Andrews Feb 16 '15 at 4:36
  • $\begingroup$ @ThomasAndrews I'm glad to hear that--I was like why do you always seem so cold and abrasive? Nice to know there was at least some context. :) $\endgroup$ – Daniel W. Farlow Feb 16 '15 at 4:51
  • $\begingroup$ @crash I try to be direct, because so many people here are not English speakers, so being indirect or obtuse with suggestions can easily be misunderstood. But I was a little cranky tonight due to something else. $\endgroup$ – Thomas Andrews Feb 16 '15 at 5:30
4
$\begingroup$

We first want to consider how we can determine the value of $9^x\pmod{1000}$ for arbitrary $x$ and, then move on to determining $x$ sufficiently well. In particular, $9$ is coprime to $1000$ and is thus a member of the multiplicative group mod $1000$. It follows quickly that, since the order of the multiplicative group mod $1000$ is $400$ (the totient of $1000$) the order of $9$ mod $1000$ (i.e. the least exponent such that $9^x\equiv 1$) must divide $400$. In particular, some computation shows that $$9^{50}\equiv 1\pmod{1000}.$$ This means to determine $9^x\pmod{1000}$, we only need to know $x$ mod $50$.

Here $x=9^{9^9}$. Now, we have reduced the problem to a simpler, analogous one. Simply apply the same steps as above to reduce it again - that is, figure out the lowest $y$ such that $9^y\equiv 1\pmod{50}$, then determine $9^9$ mod that. It's a bit of grunt work, but it's relatively straightforwards if you understand the first reduction.

$\endgroup$
  • 3
    $\begingroup$ In fact you can save some work by calculating charmicael's lambda instead of Euler's totient. $\endgroup$ – Jorge Fernández Hidalgo Feb 16 '15 at 4:13
  • 1
    $\begingroup$ This is pretty cool. The problem is that if you end up with x as 49 (or some large # mod 50), it would take a bit of time to figure out. $\endgroup$ – thang Feb 16 '15 at 4:14
  • $\begingroup$ @thang Well, $49$ wouldn't be so bad since $49\equiv -1 \pmod{50}$ and then you're just calculating $9^{-1}$ mod $1000$, which isn't too hard. Unfortunately, the exponent actually comes out as $39$ mod $50$, which is pretty much as inconvenient as it could be. It's not undoable by hand, but it wouldn't be fun either. $\endgroup$ – Milo Brandt Feb 16 '15 at 4:21
  • 2
    $\begingroup$ The nice thing is that a "tower of $9$'s mod $1000$" of any size $> 3$ gives the same answer. $\endgroup$ – Robert Israel Feb 16 '15 at 4:23
  • $\begingroup$ is it true that for any $k$ a "tower of $9\bmod 10^k$" of any size $>b$ gives the same answer? $\endgroup$ – Jorge Fernández Hidalgo Feb 16 '15 at 4:26
4
$\begingroup$

In order to compute $9^{9^{9^9}}\pmod{1000}$ we just need to compute $9^{9^9}\pmod{400}$, since $\phi(1000)=400$. So we just need to compute $9^9\pmod{160}$, since $\phi(400)=160$. Luckily, $$ 9^8\equiv 1\pmod{160} $$ by the Chinese remainder theorem $\!\!\pmod{32}$ and $\!\!\pmod{5}$, so we just need to compute $9^9\pmod{400}$. Since $9^9\equiv 14\pmod{25}$ and $9^9\equiv 9\pmod{16}$, we have: $$ 9^{9^9}\equiv 9^9 \equiv 89\pmod{400} $$ and the problems boils down to finding: $$ 9^{89}\pmod{5^3},\qquad 9^{89}\pmod{8}.$$ The second one is easy: $9^{89}\equiv 1\pmod{8}$. The first one can be deduced from:

$$\begin{eqnarray*} 9^{89}=(10-1)^{89}&\equiv& (-1)^{89}+\binom{89}{1}10(-1)^{88}+\binom{89}{2}10^2(-1)^{87}\\&\equiv&-1+890-8900\cdot44\\&\equiv&-1+15-15\cdot440\\&\equiv&-1-15\cdot 64\equiv -86\equiv 39\pmod{125}\end{eqnarray*}$$ and the Chinese theorem gives: $$9^{9^{9^9}}\equiv 9^{89} \equiv\color{red}{289}\pmod{1000}.$$

$\endgroup$
  • 2
    $\begingroup$ in fact you only need to compute $9^{9^9}\bmod 100$ since $\lambda (1000)=100$ $\endgroup$ – Jorge Fernández Hidalgo Feb 16 '15 at 5:01
  • 1
    $\begingroup$ The computation is simplified if we write $9^{89}\pmod{125}$ as $9^{-11}\pmod{125}$. $\endgroup$ – Jack D'Aurizio Feb 16 '15 at 5:01
  • 1
    $\begingroup$ On the other hand, the multiplicative order of 9 mod 100 is 10, which means we only need to find $9^9$ mod 10, which is 9 since 9 is odd, so $9^{9^9} \mod 100= 9^9\mod 100=89$. $\endgroup$ – thang Feb 16 '15 at 5:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.