Last two digits of $2^{1000}$ via Chinese Remainder Theorem? I bumped across the aforementioned question in my notes while studying today and I have completely forgot how to do this. I remember using CRT to solve a problem like this on one of my tests, too bad they didn't give back my solutions :(.
Since $\gcd(100,2) = 2$, we can't use the usual Euler's theorem to solve via $\pmod {100}$. So $100 = 5^2 2^2$, and applying Euler's on the 25 gives me $2^{20} \equiv 1 \pmod {25}$. However since $\gcd(2,4) = 2$, we can't do the same for $\bmod 4$. Accordingly how do I set up the other modulo congruence so I can apply CRT?

You have that $2^{20}\equiv 1\pmod{25}$ (thanks to Euler's Theorem), and therefore that $2^{1000} = (2^{20})^{50}\equiv 1\pmod{25}$. 
For the congruence modulo $4$ you don't even need to invoke Euler's Theorem; you can just note that since $2^2\equiv 0\pmod{4}$, then $2^{1000}\equiv 0 \pmod{4}$. So the system of congruences you have is:
$$\begin{align*}
x &\equiv 1\pmod{25}\\
x &\equiv 0 \pmod{4}
\end{align*}$$
There is one and only one number modulo 100 that satisfies both these congruences by the Chinese Remainder Theorem (it is $x\equiv 76\pmod{100}$). Since $2^{1000}$ satisfies both congruences, the CRT tells you that...
(The use of Euler's Theorem was just to simplify the computation of $2^{1000}$ modulo $25$; but to find out $2^{1000}$ modulo $4$, there is no need to simplify it, it is already very simple.)
