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?

-
If you want a similar problem that does use the CRT: what are the last two digits of $3^{1000}$? – Michael Lugo Apr 21 '11 at 4:55

You have that $2^{20}\equiv 1\pmod{25}$ (thanks to Euler's Theorem), and therefore that $2^{1000} = (2^{20})^{500}\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.)

-
Yeah I had that in mind but it seemed completely wrong for some reason, probably because we have it being congruent to 0. Hah. Thanks again! – Room Apr 21 '11 at 3:35
Is that a typo? that (2^20)^500 == 2^1000 ? – Sam Stoelinga Oct 21 '13 at 4:18

$\rm n = (2^{10})^{100} =\: 1024^{100}\: \equiv\ 0\ (mod\ 4);\:\ n\equiv (-1)^{100}\equiv 1\equiv -24\ (mod\ 25)\$ so $\rm\: n \equiv\: -24\ (mod\ 100)$

The above proof is completely elementary: it doesn't use the Fermat / Euler theorem nor the Chinese remainder theorem - only $\rm\ 4,\:25\ |\ n+24\ \Rightarrow\ lcm(4,25)\ |\ n+24\:,\$ i.e. $\rm\ 100\ |\ n+24\:.$ Granted it assumes known $\rm\ 2^{10} = 1024 = 1K\:,\:$ but that's ubiquitous in the age of the computer!

Note how much simpler this is than applying brute-force CRT + Euler/Fermat. Many similar problems can also be solved more simply in this way (thanks to the Law of Small Numbers).

-

You're almost there. From $2^{20} \equiv 1 \bmod {25}$ you get $2^{22} \equiv 4 = 2^2 \bmod {100}$, and that's the cycle you're looking for.

-