Number Theory : What are the last three digits of $9^{9^{9^9}}?$

Solution 1:

$(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$.

Solution 2:

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.

Solution 3:

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}.$$