3
$\begingroup$

Solve the following system of congruences using the Chinese remainder theorem: $$\begin{align*} 2x &\equiv 3 \pmod{7} \\ x &\equiv 4 \pmod{6} \\ 5x &\equiv 50 \pmod{55} \end{align*} $$ I was a little confused how to reduce the congruences into a form where the Chinese remainder theorem is applicable.

$\endgroup$
2
$\begingroup$
  1. The first congruence takes the form $$2x \equiv 3 \pmod 7$$ so we want to find the multiplicative inverse of $2$, modulo $7$. You can use Euclid's algorithm for computing GCDs, or just think about it, and see that $4$ is the multiplicative inverse of $2$, as $$2 \times 4 \equiv 1 \pmod{7}$$ So now we multiply the congruence through by $4$, and we get $$x \equiv 3 \times 4 \equiv 5 \pmod 7$$ which is the form we want for the CRT.

  2. This congruence is already in the form we want.

  3. The third congruence is $$5x \equiv 50 \pmod {55}$$ Since the coefficient of $x$, the remainder and the modulus all have common factor $5$, we can divide through by this to get the congruence $$x \equiv 10 \pmod {11}$$ So now this congruence is in a suitable form to apply CRT.

    (For proof that this works, observe that $$55 \mid (5x - 50) \iff 5 \times 11 \mid 5\,(x - 10) \iff 11 \mid x - 10.) $$

Now you have the three congruences $$ \begin{align*} x &\equiv 5 \pmod 7 \\ x &\equiv 4 \pmod 6 \\ x &\equiv 10 \pmod {11} \end{align*} $$ the standard form, which I assume you already know how to solve.

$\endgroup$
  • $\begingroup$ isn't the first congruence x≡5 (mod 7) since 12-7=5? $\endgroup$ – Lil May 2 '14 at 20:56
  • $\begingroup$ @Lil: Yes, my mistake copy/pasting from top to bottom. Fixed. $\endgroup$ – alexwlchan May 2 '14 at 20:57
  • $\begingroup$ np, one more question. what is the solution to the congruence 4x≡1(mod6)? $\endgroup$ – Lil May 2 '14 at 21:01
  • $\begingroup$ @Lil: No solution exists. Observe that $4x \equiv 1 \pmod 6$ is equivalent to $6 \mid (4x - 1)$, but $(4x - 1)$ is odd for any choice of $x$, so we cannot have $6 \mid (4x - 1)$ (as $6$ is even). $\endgroup$ – alexwlchan May 2 '14 at 21:03
  • $\begingroup$ so how do you go about solving this using the chinese remainder theorem? Should I just solve the other 2 congruences and then substitute the number back in for x? $\endgroup$ – Lil May 2 '14 at 21:03
1
$\begingroup$

The congruence $2x\equiv 3\pmod{7}$ holds if and only if $x\equiv 5\pmod{7}$. And $5x\equiv 50\pmod{55}$ if and only if $x\equiv 10\pmod{11}$. Now the problem is in "standard" form.

Remark: To get the first result, we can multiply both sides of $2x\equiv 3\pmod{7}$ by the inverse of $2$ modulo $7$. Note that $4$ is the inverse to $2$. Or more simply we replace the $3$ by $10$, and divide by $2$.

The second result comes from the general fact that if $k\ne 0$, then $ka\equiv kb\pmod{km}$ if and only if $a\equiv b\pmod{m}$.

$\endgroup$
  • $\begingroup$ so for the congruence: 5x≡50(mod55) you just divided everything by 5 to simplify correct? How did you simplify 2x≡3(mod7) $\endgroup$ – Lil May 2 '14 at 20:48
  • $\begingroup$ I added a bit in a remark. $\endgroup$ – André Nicolas May 2 '14 at 20:50
  • $\begingroup$ got it. Thank you so much! $\endgroup$ – Lil May 2 '14 at 20:51
  • $\begingroup$ what is the solution to the congruence 4x≡1(mod6) I can't think of any number smaller than 6 for x that makes the statement true. $\endgroup$ – Lil May 2 '14 at 20:52
  • $\begingroup$ You are welcome. The answer just posted by alexwichan has thorough explanations. $\endgroup$ – André Nicolas May 2 '14 at 20:53
0
$\begingroup$

Solving x = 5(mod 7) and x = 4(mod 6) simultaneously, you get x = 40(mod 42).

Solving this result and x = 10(mod 11) simultaneously, you get x = 208(mod 462)

Which is the final answer.

$\endgroup$
0
$\begingroup$

$$2x≡3(mod 7)=> 2x≡3+7(mod 7)$$

$$x≡4(mod 6)$$

$$5x≡50(mod 55) => x≡10(mod 11)$$

3 linear congruence formed now apply CRT

$$m=7*6*11=462$$

$$M_1=66,M_2=77,M_3=42$$

$$66x≡1(mod 7) ; b_1=5$$

$$77x≡1(mod 6) ; b_2=-1$$ $$42x≡1(mod 11) ; b_3=5$$

$$x≡5*5*66+77*(-1)*(4)+42*5*10(mod 462)$$

$$x≡3442 (mod 462)$$

$$x≡208(mod 462)$$

$$x=(462)t+208; t={0,1,2,3...}$$

$\endgroup$
  • $\begingroup$ Please use MathJax. $\endgroup$ – José Carlos Santos Aug 31 '17 at 15:54
  • $\begingroup$ Thanks for the link, will study and implement it. $\endgroup$ – shaurya uppal Aug 31 '17 at 17:08

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.