7
$\begingroup$

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?

  • 0
    If you want a similar problem that does use the CRT: what are the last two digits of $3^{1000}$?2011-04-21

3 Answers 3

9

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

  • 1
    Is that a typo? that (2^20)^500 == 2^1000 ?2013-10-21
6

By $\ ab\,\bmod\, \color{#90f}{ac}\, =\ a\,(b\bmod c)\, =\, $ mod Distributive Law $ $ & $\,\overbrace{\color{#0a0}{2^{\large 10}}\! = 1024\equiv -1\pmod{\!25}}^{\Large {\rm or}\ \ \color{#0a0}{2^{\LARGE 20}}\equiv\ 1\ \ {\rm by\ Euler\ \phi}}\,$

$\ \ \, 2^{\large 20J}\!\! \bmod \color{#90f}{100}\, =\, 4\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\underbrace{\left[\dfrac{\color{#0a0}{2}^{\large\color{#0a0}{20}J}}4\!\bmod 25\right]}_{\large\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \equiv\ {\small\dfrac{1}4}\equiv\ {\small\dfrac{-24}4}\,\ \equiv\ -6\ \ \equiv\ \ \color{#c00}{19}}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! = 4[\color{#c00}{19}] = 76$ $\, \left\{\!\begin{align} &\text{mDL is an ${\it operational}$ version of CRT,}\\ &\!\text { as explained in the prior linked answer.}\end{align}\right.$

0

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.