Find the remainder of $3^{333}$ divided by $100$

Question

Find the remainder of $3^{333}$ divided by $100$

So I can find that $100=2^2\cdot 5^2$

Then I want to find $3^{333}$ mod $4$ and mod $25$ and use chinese remainder theorem to find a solution mod $100$.

I can find that $3^{333}\equiv (-1)$ mod $4$

But then $3^{333}=((3^3)^3)^{37}\equiv (27^3)^{37}\equiv (2^3)^{37}\equiv 8^{37}$ mod $25$

But I cannot find $8^{37}$ mod $25$

Answer 1

We have $3^{333} \equiv 2^{111}\equiv1024^{11}\times2\equiv-2 \pmod{25}$ (note that I used your calculation for the first equality here and the well-known fact that $2^{10}=1024$)

So, if $x=3^{333}$, $x=-2+25k \equiv-2+k \equiv-1 \pmod4$

Hence $k \equiv1 \pmod 4$

Therefore $x=-2+25(1+4k')=23+100k' \equiv23 \pmod{100}$