$9^{123456789} \pmod{100}$ , retrace calculation operation I have $9^{123456789} \pmod {100}$. I did use Euler's Theorem, and got $\phi = 40$ and therefore I can say $$9^{123456789 \pmod {40}} \pmod {100} \equiv 9^{29} \pmod {100}$$ Then in one of my notes it said that this is equivalent to $9^{29 \pmod {20}} \pmod{100}$ and therefore $9^9 \pmod{100}$. I do not understand how you are supposed to get the $\pmod{20}$ up in the exponent, I mean it's probably Euler-Fermat but I just don't see how.

Remember that $9=3^2$. From Euler's theorem we know that $3^{40}\equiv 1\pmod {100}$, so that $9^{20}\equiv 1\pmod{100}$.