Fun with Exponents

[molotom]

Not exactly elegant, but here goes:

Lemma:
9^10 = 1 mod 100
9^100 = 1 mod 1000
9^1000 = 1 mod 10000
etc

Let f(n) = 9^9^...^9 containing n nines.

f(1) = 9 = -1 mod 10
f(n+1) = f(1)^9 = (-1)^9 = -1 mod 10
So f(n) = -1 mod 10 , for all n>1. Therefore the last digit is 9.

Now for n>2:
f(n) = 9^f(n-1) = 9^(10a + b) where b = f(n-1) mod 10
But 9^10 = 1 mod 100 (by lemma), and f(n-1) = -1 mod 10, therefore:
f(n) = 9^b = 9^(-1) = -11 = 89 mod 100

Similarly
f(n) = 9^89 = 289 mod 1000

f(n) = 9^289 = 5289 mod 10000

f(n) = 9^5289 = 45289 mod 100000

Note that this holds for all n > 5