1. ## Last 5 digits

find the final 5 digits of,

$\displaystyle 9^{9^{9^{^{.^{.^{.^{.^{9}}}}}}}}$ that is 1001 nines

2. ## A computing approach

Define $\displaystyle f(x)=9^x$. So $\displaystyle f^2(x)=f(f(x))=9^{9^x}$ and so on. Phrased this way, we are asked to calculate $\displaystyle f^{1000}(9) (\bmod 100000)$. By nature of modular arithmetic, it does not matter if we calculate $\displaystyle f^{1000}(9)$ first, then reduce it modulo 100000, or if we calculate f(9), reduce it, then calculate f of the reduced answer, and so on. In other words, we can iterate via:

$\displaystyle x_0=9, x_{n+1}\equiv 9^{x_n} (\bmod 100000)$

Iterating 1000 times, reducing the answer each time. Setting this ball in motion, we get:

$\displaystyle 9\to 20489 \to 77289 \to 65289 \to 45289 \to 45289 \to 45289 ...$

Here we notice that $\displaystyle f^5(9)=f^6(9)$ and therefore $\displaystyle f^n(9)=f^5(9)=45289$ for all $\displaystyle n>5$. In other words, we found a fixed point in the function f and need go no further. Namely, $\displaystyle 9^{45289}\equiv 45289 (\bmod 100000)$. Thus we have found our answer.

This seems like an odd coincidence, and begs the general question: Given a,b, for what value of x does $\displaystyle a^x\equiv x (\bmod b)$, and for what values a,b does no such x exist?