Finding $9^{123456789} \pmod{100}$

Question

$9^{123456789} \pmod{100}$

I tried to do this in a simpler way:

$$9 \equiv 9 \pmod{100}$$

$$9^1 \equiv 09 \\ 9^2 \equiv 81 \\ 9^3 \equiv 29 \\ 9^4 \equiv 61 \\ 9^5 \equiv 49 \\ 9^6 \equiv 41 \\ 9^7 \equiv 69 \\ 9^8 \equiv 21 \\ 9^9 \equiv 89 \\ 9^{10} \equiv 01$$

I noticed that the odd powers always end in 9 and the even ones in $1$. The leftmost digit follows the sequence $0,2,4,6,8,$... in this order for odd numbers and the other way around for even ones. The sequence has $5$ numbers.

$123456789$ is an odd number. $123456789 \equiv 4 \pmod 5$ so the answer should be $69,$ which is the $4$th of the sequence... but it's $89.$ Close enough, but not quite. What did I do wrong and how can I solve this in this way?

Answer 1

$$ 9^{10} \equiv 1 \pmod {25} $$

Answer 2

Given your column of results, \begin{align*} 9^{123456789} &= 9^{12345678 \cdot 10 + 9} \\ &= (9^{10})^{12345678}9^9 \\ &\cong 1^{12345678} \cdot{89} \pmod{100} \\ &\cong 89 \pmod{100} \text{.} \end{align*}

Answer 3

Using Binomial Theorem, we get

$$9^{123456789}=(-1+10)^{123456789}\equiv(-1)^{123456789}+123456789\cdot10^1\cdot(-1)^{123456789-1}\equiv-1+90\equiv89 \pmod{100}$$