2
$\begingroup$

I am really stuck on this problem.

Solve the following system of simultaneous congruences

$X + 3Y \equiv 2 \pmod5 \hspace{50pt} X+2Y \equiv 3 \pmod5$

$ X + 2Y \equiv 3 \pmod7 \hspace{50pt} 2X + Y \equiv 4 \pmod7$

Using the Chinese Remainder Theorem I have found separate solutions to

$ 1) \hspace{5pt} x \equiv 2 \pmod 5 \hspace{30pt} and \hspace{30pt} 2) \hspace{5pt} x \equiv 3 \pmod 5$

$ \hspace{12pt}x \equiv 3 \pmod 7 \hspace{30pt} \hspace{58pt} x \equiv 4 \pmod 7$

These are $x =17$ for $ \ 1) \ $ and $ \ x = 18$ for $ \ 2)$. Is this even the right way to proceed, and if it is where do you go from here?

Any help would be really good!

  • 0
    I wonder, is there a matrix version of the Chinese Remainder Theorem? Ah, here is one [paper](http://www.math.harvard.edu/~knill/preprints/linear.pdf).2012-03-19

2 Answers 2

5

Hint $\ $ It's a simple constant case of CRT: $\:\!$ if $\rm\:gcd(m,n)=1\:$ then $\rm\:lcm(m,n) = mn,\:$ hence

$\rm\qquad\ \ \ x \equiv a\pmod{m,n}\iff m,n\ |\ x-a\iff mn\ |\ x-a\iff x\equiv a\pmod{mn}$

Thus $\rm\:\!\ \ X+2Y \equiv 3\ \:(mod\ 5,7)\iff X+2Y \equiv 3\pmod{35}\qquad\quad\ \ \ [1]$

and $\rm\ \ \ \: 2X+Y \equiv 4\ \:(mod\ 5,7)\iff 2X+Y \equiv 4\pmod{35}\qquad\quad\ \ \ [2]$

Now $\rm\ 2\cdot [1] - [2]\ \Rightarrow\: 3Y\equiv 2 \equiv -33\ \Rightarrow\ Y \equiv -11\ \Rightarrow\ X \equiv 3-2Y \equiv 25$

Remark $\ $ This simple constant-case optimization of CRT arises quite frequently in practice, esp. for small moduli (by the law of small numbers), so it is well worth checking for. For further examples, see here where it simplified a few page calculation to a few lines, and here and here.

  • 0
    Thank you very much that makes alot of sense! Also thanks for all the useful links.2012-03-20
1

First solve the two congruences modulo 5 to get values of $x$ modulo 5 and $y$ modulo 5. Then do the same for the two congruences modulo 7. Then use Chinese Remainder Theorem to get values of $x$ and $y$ modulo 35.