How to calculate the last digits of a big number using modular arithemtic?

Question

I'm trying to calculate the last 2 digits of $9^{9^{9^{9}}}$ using modular arithmetic somehow. Please help.

Answer 1

I start with the long way that works every time. Skip to the last paragraph for a very short solution in this case.

---

Your goal is to compute $$ 9^{9^{9^9}}\pmod{100}. $$

One way to compute this is to use Euler's totient function $\varphi$. Since the totient function is multiplicative, $$ \varphi(100)=\varphi(2^2)\varphi(5^2)=(2^2-2^1)(5^2-5^1)=2\cdot 20=40. $$

Euler's theorem states that $$ a^{\varphi(100)}\equiv 1\pmod{100} $$ for $a$ relatively prime to $100$. Therefore, it is enough to compute $$ 9^{9^{9^9}\pmod{\varphi(100)}}\pmod{100}. $$

Therefore, our problem is reduced to $$ 9^{9^9}\pmod{40}. $$ By following the same pattern, we see that $$ \varphi(40)=\varphi(2^3)\varphi(5)=(2^3-2^2)(5^1-5^0)=4\cdot 4=16. $$ Therefore, we need to compute $$ 9^{9^9\pmod{\varphi(40)}}\pmod{40}. $$ Therefore, our problem reduces to computing $$ 9^9\pmod{16}. $$ Following in our pattern, it is enough to compute $$ 9^{9\pmod{\varphi(16)}}. $$ Since $\varphi(16)=2^4-2^3=8$, we know that $$ 9^9\equiv 9^1=9\pmod{16}. $$ Therefore, $$ 9^{9^9}\equiv 9^9\pmod{40}. $$ Moreover, since $9^9=9\cdot 9\cdot 9\cdot 9\cdot 9\cdot 9\cdot 9\cdot 9\cdot 9$, and $9\cdot 9=81\equiv 1\pmod {40}$, $9^9\equiv 9\pmod{40}$.

Putting this together, $$ 9^{9^{9^9}}\equiv 9^9\pmod{100}. $$ Now, this is fairly straight-forward to compute since $$ 9^9=(9^3)^3. $$ Since $9^3=729\equiv 29\pmod{100}$, we have that $$ 9^{9^{9^9}}\equiv 9^9\equiv (29)^3\pmod{100}. $$ Since $$ 29^3=24389\equiv 89\pmod{100}, $$ we have that $$ 9^{9^{9^9}}\equiv 9^9\equiv (29)^3\equiv 89\pmod{100}. $$ Therefore, the last two digits are $89$.

---

It is faster, however, to notice that $9^{10}\equiv 1\pmod{100}$, so we only need to compute $9^{9^9}\pmod{10}$ because multiples of $10$ in the exponent correspond to multiplying by $1\pmod{100}$. Therefore, all we need is the remainder modulo $10$ in the exponent, i.e., $$ 9^{9^{9^9}}\equiv 9^{9^{9^9}\pmod{10}}\pmod{100}. $$ Since $9\equiv -1\pmod{10}$, and $9^9$ is odd, we know that $9^{9^9}\equiv -1\equiv 9\pmod{10}$. Therefore, the original expression is equivaent to $9^9\pmod{100}$, which can be calculated as above (or on a calculator).