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$
On
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}$
On
Use the totient function. $2$ and $5$ are distinct primes so $\phi(100)=\phi(2^25^2)=\phi(2^2)\phi(5^2)=[2(2-1)][5(5-1)]=40.$
Now since $\gcd(3,100)=1$ we have $1\equiv 3^{\phi(100)}\equiv 3^{40} \mod 100.$
Therefore $3^{333}\equiv (3^{40})^8\cdot 3^{13}\equiv (1)^8\cdot 3^{13}\equiv 3^{13} \mod 100.$
To finish, see my comment to the Q.
On
$4\mid 100\:$ & $\:4\mid \color{#90f}{3^{333}}\!+1\,$ (by $\bmod 4\!:\ 3^{333}\!+1\equiv (-1)^{333}\!+1\equiv -1+1\equiv 0),\,$ so
using $\ ab\bmod ac = a\,(b\bmod c) = $ mod Distributive Law to factor out $\,a = 4$
$3^{\large 333}\!+\!1\bmod 100 = 4\left[\dfrac{\color{#90f}{3^{\large 333}}\!+\!1}4\bmod 25\right] = 4\left[\dfrac{\color{#90f}{23}\!+\!1}4\bmod 25\right] = 4[6],\ $ by
$\!\bmod 25\!:\,\ \color{#c00}{3^{\large 20}\equiv 1}\ \Rightarrow\ \color{#90f}{3^{\large 333}}\equiv \underbrace{3(\color{#0a0}{3^{\large 3}})^{\large 4}(\color{#c00}{3^{\large 20}})^{\large 16}}_{\textstyle 3\,(\color{#0a0}2)^{\large 4}\,\color{#c00}1^{\large 16}}\equiv \color{#90f}{23},\,$ by $\rm\color{#c00}{Euler\ \phi(5^2)=4\cdot 5}$
Remark $ $ The computation of $\,\color{#90f}{3^{333}}\bmod 25\,$ in the prior line is a special case of the method of modular order reduction - the key to simplifying the computation of large modular powers.
As explained in the first link, the mod Distributive Law is an operational form of CRT. We can use the standard CRT formula along with the above computation mod $25$ to obtain the same result. In fact already $23\equiv -1\pmod{\!4}$ so we're done - we don't even need to apply the CRT formula.
Another quick way: $\, 3^{\large 333} = 3(-1+10)^{\large 166} =\,\ldots\,$ so expanding by Binomial Theorem shows only the first $2$ terms survive $\!\bmod 100 = 10^2$.
On
Use Euler.
$\phi(25) = 20$ so $8^{20}\equiv 1 \pmod {25}$
So we need to figure out $8^{17}\equiv 8^{-3}$ which is which will be equivalent to $k^3$ where $k$ is the multiplicative inverse of $8$. $8*3=24\equiv -1$ so $8*(-3)\equiv 1 \pmod{25}$ and $8^{17} \equiv (-3)^3 \equiv -27\equiv -2\equiv 23 \pmod {25}$.
.....
Or back to the $3$
$3^{333}=3^{320}3^{13}\equiv 3^{13}\pmod {25}$.
As $3^{20}\equiv 1$ its a good guess that $3^{10} \equiv \pm 1$.
Many ways to do this but $3^{10} = 3^3*3^3*3^3*3\equiv 27*27*27*3\equiv 2*2*2*3\equiv 24 \equiv -1 \pmod {20}$. So $3^{13}\equiv -3^3\equiv -27\equiv -2 \equiv 23$.
.....OR.....
$100 = 10^2$
$3^2 = 10-1$
So $3^{10} = (10-1)^5\equiv 50-1$
$3^{20} \equiv (50-1)^2 \equiv 1\pmod {100}$.
So $3^{333}\equiv 3^{13}\equiv 3^{10}*3^{3}\equiv (50-1)*27\equiv 50*(26+1)-27\equiv 50 - 27 \equiv 23\pmod{100}$
On
$3^{333}$ being divided by 100.
$=(3^9)^{37}$
$=19683^{37}$
$=(19700-17)^{37}$
$\equiv -17^{37} \quad \bmod 100$
$-17^{37} =-17(17^{36})=-17(300-11)^{18}$
$\equiv -17(11^{18}) \quad \bmod 100$
$-17(11^{18})=-17((1300+31)^6)$
$\equiv -17(31^6) \quad \bmod 100$
$-17(31^6)=-17(1000-39)^3$
$\equiv -17 \cdot -39^3 \quad \bmod 100$
$17 \cdot 39^3=17 \cdot 39 \cdot (1500+21)$
$=(700-37)(1500+21)$
And after all the work $-37 \cdot 21=-777 \equiv -77 (\bmod 100)$
But if the answer had to be positive then $100-77=\boxed{23}$
So you need, as you noted, $3^{13}\pmod {100}$. Try successive squaring. $3^2=9,3^4=9^2=81,3^8=81^2=(-19)^2=61, 3^{12}=3^4\cdot3^8=81\cdot61=41,3^{13}=3\cdot41=23\pmod{100}$.