# Find the last two digits of $9^{{9}^{9}}$

I have to find the last two decimal digits of the number $9^{{9}^{9}}$.

That's what I did:

$$m=100 , \phi(m)=40, a=9$$ $$(100,9)=1, \text{ so from Euler's theorem,we have :} 9^{40} \equiv 1 \pmod{100}$$

$$9^{{9}^{9}} \equiv 9^{9^{2+2+2+2+1}} \equiv 9^{9^2 \cdot 9^2 \cdot 9^2 \cdot 9^2 \cdot 9} \equiv 9^{81 \cdot 81 \cdot 81 \cdot 81 \cdot 9} \equiv 9^{(40+40+1) \cdot (40+40+1) \cdot (40+40+1) \cdot (40+40+1) \cdot 9} \equiv (9^{(40+40+1)})^{(40+40+1) \cdot (40+40+1) \cdot (40+40+1) \cdot 9} \equiv 9^9 \equiv 9^4 \cdot 9^4 \cdot 9 \equiv 6561 \cdot 6561 \cdot 9 \equiv 3721 \cdot 9 \\ \equiv 21 \cdot 9 \equiv 89 \pmod{100}$$

So,the last two digits are $8 \text{ and } 9$. But,is there also an other way two calculate the last two digits of $9^{{9}^{9}}$ or is the above the only one?

-
The Chinese remainder theorem might help, but this looks efficient enough already. You have a typo, by the way, the last equation should be mod 100 :) – Thomas Jun 21 '14 at 14:23
@Thomas How could I use the Chinese remainder theorem? – evinda Jun 21 '14 at 14:42
From your calculation you want the exponent $\mod 40$. So you want $9^9 \mod 40$, but as you show $9^2=1 \mod 40$ so $9^9=9 \mod 40$ and then $9^{9^9}=9^9 \mod 100$ – i. m. soloveichik Jun 21 '14 at 15:35
From Euler you get that $a^{\phi(100)}\equiv a^{40} \equiv 1 \pmod{100}$. The Chinese remainder theorem gives the sharper $a^{\text{lcm}(\phi(2^2),\phi(5^2))}\equiv a^{20} \equiv 1 \pmod{100}$. This is also known as Carmichael's theorem. – I like Serena Jun 21 '14 at 19:07
Got something from an answer? – Did Mar 12 '15 at 7:23

Key remark: By the binomial theorem, $(10-1)^k=\cdots+10\cdot k-1$ where $\cdots$ is a multiple of $100$. Since $10\cdot k=10\cdot i\pmod{100}$ where $i$ denotes the last digit of $k$, this shows that, for every $k$, $9^k=10\cdot i-1\pmod{100}$.

For $k=9$, $i=9$ hence the key-remark yields $9^9=10\cdot i-1=89\pmod{100}$.

In particular, the last digit of $\ell=9^9$ is $j=9$ hence, re-using the key-remark, one gets $9^{9^9}=10\cdot j-1=89\pmod{100}$.

And so on: for every tower of nines, $9^{9^{9^{9^{\cdots}}}}=89\pmod{100}$.

-

You could also just do modular exponentiation and take note of the periods.

The powers of $9 \mod 100$ are: 1, 9, 81, 29, 61, 49, 41, 69, 21, 89, 1, 9, 81, 29, 61, 49, ... They have a period of $10$. This means that if $n \equiv 9 \mod 10$, then $9^n \equiv 89 \mod 100$. Since $9^9 = 387,420,489$, this means that $9^{9^9} \equiv 89 \mod 100$.

-

Let $k$ be the order of $9$ mod $100$. Then $$1\equiv 9^k=(10-1)^k \equiv 10\binom{k}{1}\cdot 10(-1)^{k-1}+(-1)^k\pmod{100}$$ It implies that $1=\pm (10k-1)\pmod{100}$. The minimal integer which satisfies this condition is $k=10$. It follows that $$9^{9^9} \equiv 9^9 \equiv 9^{-1}\equiv 89\pmod{100}.$$

-