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

  • $\begingroup$ Wow that's pretty smart. Thanks buddy! $\endgroup$ – 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}$


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

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


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

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

Can you take it from here?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.