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$ – Bill Dubuque Oct 16 '18 at 0:38
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$ – Antoni Parellada Jan 21 '18 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 '18 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$ – Antoni Parellada Jan 21 '18 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 '18 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 '18 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$ – Antoni Parellada Jan 21 '18 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$ – Mohammad Riazi-Kermani Jan 21 '18 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$ – Antoni Parellada Jan 21 '18 at 22:48
  • $\begingroup$ Correct, you have the formula for systems in general. $\endgroup$ – Mohammad Riazi-Kermani Jan 21 '18 at 23:49
  • $\begingroup$ Thank you. I upvoted. $\endgroup$ – Antoni Parellada Jan 22 '18 at 1:34
3
$\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$ – Antoni Parellada Jan 21 '18 at 22:01
  • $\begingroup$ Thanks you for your attention to details. $\endgroup$ – Mohammad Riazi-Kermani Jan 21 '18 at 23:53
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 '18 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 '18 at 21:49
  • $\begingroup$ Yes, but there exists an effective CRT, fairly simple in the case of two congruences. $\endgroup$ – Bernard Jan 21 '18 at 21:53
  • $\begingroup$ @Bernard Yes indeed it is precisely the link I've given! :) $\endgroup$ – user Jan 21 '18 at 21:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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