Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

3 Answers 3

up vote 6 down vote accepted

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.)

share|improve this answer
    
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
add comment

$\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).

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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