4
$\begingroup$

I am trying to get an idea of how the Chinese Remainder Theorem (CRT) can be used to finish up this problem, in which the problem

$$7^{30}\equiv x\pmod{ 100}$$

is attempted by splitting the modulus into relatively prime factors $25$ and $4,$ arriving at

$$\begin{align} 7^{30}&\equiv1\pmod4\\ 7^{30}&\equiv-1\pmod{25} \end{align}$$

I understand that the CRT may be called upon because $m=\prod m_i,$ and we have the same $7^{30}$ value on the LHS, but I don't know how to carry it out.

The question was touched upon in this post as the second entry:

How do I efficiently compute $a^b \pmod c$ when $b$ is less than $c.$ For instance $5^{69}\,\bmod 101.$

However, I don't see this particular point clearly worked out, perhaps because it is a multi-pronged question.


Following this presentation online, this seems to be the verbatim application of the CRT without any added concepts or shortcuts:

From @gimusi's answer (upvoted):

$$\begin{cases} x \equiv 7^{30} \pmod4\\ x\equiv 7^{30} \pmod{25} \end{cases}$$

rearranged into

\begin{cases} x \equiv 1 \pmod4\\ x\equiv -1 \pmod{25} \end{cases}

Given the general form of the equations above as $x\equiv a_i \pmod {m_i},$ the CRT states $x\equiv a_1 b_1 \frac{M}{m_1}+a_2 b_2 \frac{M}{m_2}\pmod M$ with $M=\prod m_i,$ and with

$$b_i =\left(\frac{M}{m_i}\right)^{-1}\pmod {m_i}.$$

The inverse of $\frac{M}{m_i}$ is such that $\frac{M}{m_i}\left(\frac{M}{m_i}\right)^{-1}\pmod {m_i}\equiv 1.$

Calculating the components:

$$\begin{align} a_1&=1\\ a_2&=-1\\ M&=4\times 25 =100\\ \frac{M}{m_1} &= \frac{100}{4}=25\\ \frac{M}{m_2} &= \frac{100}{25}=4\\ b_1 &= \left(\frac{M}{m_1}\right)^{-1} \pmod 4 = (25)^{-1}\pmod 4 =1\\ b_2 &= \left(\frac{M}{m_2}\right)^{-1} \pmod {25}= (4)^{-1} \pmod{25}=19 \end{align}$$

Hence,

$$x=1\cdot 25 \cdot 1 + (-1)\cdot 4 \cdot 19 = -51 \pmod{100}\equiv 49.$$

$\endgroup$
1
  • $\begingroup$ Simpler to use $\ \large 7^{30} = (50-1)^{15}\ $ and then you need only the first 2 terms of the Binomial Theorem, similar to here. $\endgroup$ Oct 16, 2018 at 0:38

4 Answers 4

4
$\begingroup$

Welcome to Math SX! You have to use Euler's theorem as $\varphi(4)=2$, $\;\varphi(25)=20$ we have $$ 7^{30}\equiv7^{30\bmod2}=1\mod 4,\qquad 7^{30}\equiv7^{30\bmod20}=7^{10}\mod 25$$ To find the latter power, you can use the modular fast exponentiation algorithm, but here, it will be simpler: modulo $25$, $$7^2\equiv -1\enspace\text{so}\enspace 7^4=1,\enspace\text{hence } \;7^{30}\equiv 7^{30\bmod 4}=7^2\equiv -1.$$ Finally, since $\;25-6\cdot 4=1$ (Bézout's identity), $$7\equiv \begin{cases}\phantom{-}1\mod4\\-1\mod 25\end{cases}\iff 7\equiv 1\cdot 25-(-1)\cdot 6\cdot 4=49\mod 100.$$

$\endgroup$
7
  • $\begingroup$ Thank you. I'm not sure how to interpret expressions such as $7^{30}\equiv7^{30\bmod2}=1.$ I looked up Euler's theorem, and it led me to things like $7^{\phi(4)}\equiv 1 \pmod 4.$ $\endgroup$ Jan 21, 2018 at 21:59
  • $\begingroup$ So you can reduce the exponent modulo φ(4), which is equal to $2$. This means $7^n\equiv 7$ if $n$ is odd, ${}\equiv 1$ if $n$ is even. $\endgroup$
    – Bernard
    Jan 21, 2018 at 22:02
  • $\begingroup$ So we left it at $7^{\phi(4)}=7^2\equiv 1 \pmod 4$ and $7^{\phi(25)}=7^{20}\equiv 1 \pmod 25.$ How do you go from this to $7\equiv \begin{cases}\phantom{-}1\mod4\\-1\mod 25\end{cases}$ and the subsequent final identity? $\endgroup$ Jan 21, 2018 at 22:34
  • $\begingroup$ For the last case, I had a shortcut: $7$ has order $4$ mod. $25$, not $20$, so I simply had to reduce the exponent mod. $4$, which makes the computation, considerably simpler. $\endgroup$
    – Bernard
    Jan 21, 2018 at 22:39
  • $\begingroup$ Well, if $7^4\equiv 1$, $7^5=7^4\cdot 7\equiv 1\cdot 7=7 $, $7^6=7^4\cdot 7^2\equiv 1\cdot (-1)=-1 $, $7^7=7^4\cdot 7^3\equiv 1\cdot (-7)=-7 $, $7^8=(7^4)^2\equiv 1^2=7 $, and so on. More generally $7^{4k+r}=7^{4k} \cdot7^r\equiv 1\cdot 7^r=7^r $. $\endgroup$
    – Bernard
    Jan 21, 2018 at 23:23
4
$\begingroup$

$$7^{30}\equiv x\pmod{ 100}$$

Could be solved easily without Chinese Remainder Theorem. Note that $7^4=2401 \equiv 1\pmod {100} $ Thus $$ 7^{30} = 7^{28}\times 49 \equiv 49 \pmod {100}$$

Solving the system with Chinese Remainder Theorem requires finding a linear combination of $25$ and $4$ to equal 1.

Such a combination is $$ 1= 1(25) -6(4) $$

Therefore the answer to the system is $$ x\equiv (1)(1)(25) +(-1)(-6)(4) \pmod {100}$$

That is $$ x\equiv 49 \pmod {100}$$

$\endgroup$
5
  • $\begingroup$ I am interested in finding out how the equation $x\equiv(1)(1)(25)+(−1)(−6)(4)(\pmod100)$ comes about. $\endgroup$ Jan 21, 2018 at 21:51
  • $\begingroup$ since 1=1(25)-6(4) , in order to find an x which is equal 1 mod 4 we simply multiply 1(25) by 1 and and in order to have our x equal -1 mod 25 we multiply -6(4) by (-1) and add them up to get x= 49 mod 100. It works because of 1 is the sum of a multiple of 25 and a multiple of 4. $\endgroup$ Jan 21, 2018 at 22:06
  • $\begingroup$ So $1=1(25)-6(4)$ is Bézout's identity and $x\equiv (1)(1)(25) +(-1)(-6)(4) \pmod {100}$ is $x\equiv a_1 b_1 \frac{M}{m_1}+\cdots +a_r b_r \frac{M}{m_r}\pmod M$ in here, with $b_1=1$ and $b_2=-1$; and $a_1=1$ with $a_2=-6?$ $\endgroup$ Jan 21, 2018 at 22:48
  • $\begingroup$ Correct, you have the formula for systems in general. $\endgroup$ Jan 21, 2018 at 23:49
  • $\begingroup$ Thank you. I upvoted. $\endgroup$ Jan 22, 2018 at 1:34
3
$\begingroup$

From here

$$\begin{cases} x \equiv 7^{30} \pmod4\\ x\equiv 7^{30} \pmod{25} \end{cases}$$

by CRT we know that solutions exist $\pmod{100}$.

Then note that since $7^2=49\equiv 1 \pmod4$

$$x\equiv7^{30} \implies x\equiv 49^{15} \equiv 1\pmod4$$

and since $7^2=49\equiv -1 \pmod{25}$

$$x\equiv7^{30} \implies x\equiv 49^{15} \equiv -1\pmod{25}$$

Thus the system becomes

$$\begin{cases} x \equiv 1 \pmod4\\ x\equiv -1 \pmod{25} \end{cases}$$

Note that CRT guarantees that the solutions exist $\pmod{100}$ but doesn't give special shortcut to find the solution.

When you can't by inspection (in this case you can easily find $x=49$), in general to find the solution you can follow the procedure indicated here CRT -Case of two moduli

$\endgroup$
4
  • $\begingroup$ There is a formula based on Bézout's identity. $\endgroup$
    – Bernard
    Jan 21, 2018 at 21:44
  • $\begingroup$ @Bernard Of course you can use Bezout, what I mean is that CRT is not aimed to give the solution but to prove that solution exist, am I wrong? Of course we can use the method applied for the proof to find the solutions. $\endgroup$
    – user
    Jan 21, 2018 at 21:49
  • $\begingroup$ Yes, but there exists an effective CRT, fairly simple in the case of two congruences. $\endgroup$
    – Bernard
    Jan 21, 2018 at 21:53
  • $\begingroup$ @Bernard Yes indeed it is precisely the link I've given! :) $\endgroup$
    – user
    Jan 21, 2018 at 21:55
2
$\begingroup$

Chinese Remainder Theorem says:

$$\mathbb{Z}/100 \simeq \mathbb{Z}/25 \times \mathbb{Z}/4$$

where the isomorphism is given by mapping $x \pmod {100}$ to $(x \pmod {25}, x \pmod {4})$. Thus, the class of $x$ is a number from $0$ to $99$ that congruence to $1 \bmod 4$ and $24 \bmod 25$. The numbers $0 \le x \le 99$ and $x \equiv 24 \pmod {25}$ are: $24, 49, 74, 99$. Now which one is congruence to $1 \bmod 4$?

$\endgroup$
2
  • $\begingroup$ Thank you. It certainly helps a lot in a big picture kind of way. $\endgroup$ Jan 21, 2018 at 22:01
  • $\begingroup$ Thanks you for your attention to details. $\endgroup$ Jan 21, 2018 at 23:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .