$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}$$

this equals $9^{29} \pmod {100}$. Then in one of my notes it said that this is equivalent to $9^{29 mod {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}$.

• Wow that's pretty smart. Thanks buddy! – Somebody Jun 28 '15 at 12:13

When the modulus is composite, Carmichael function is more efficient

$\lambda(100)=20$ and $123456789\equiv9\pmod{20}$

and consequently, $9^{123456789}\equiv9^9\pmod{100}$

Again, $9=3^2\implies9^9=3^{18}$ But $(3,100)=1\implies3^{20}\equiv1\pmod{100}$

$\implies3^{18}\equiv3^{-2}\equiv9^{-1}$

As $9\cdot11\equiv-1\pmod{100},9^{-1}\equiv-11\equiv89$

Alternatively, $9^{123456789}=(10-1)^{123456789}=-(1-10)^{123456789}$

$A=(1-10)^{123456789}\equiv1-\binom{123456789}1\cdot10^1\pmod{100}$

As $123456789\equiv9\pmod{10},10\cdot123456789\equiv10\cdot9\pmod{10\cdot10}$

$\implies A\equiv1-90\pmod{100}$

Can you take it from here?