Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
I see four equations in $x,y$... Do they correspond to two different sets of equations? –  TMM Mar 19 '12 at 23:40
    
No I don't think they do. I am pretty sure you have to find a $X$ and $Y$ that satisfies all four at once. –  Alex Kite Mar 19 '12 at 23:44
    
I wonder, is there a matrix version of the Chinese Remainder Theorem? Ah, here is one paper. –  lhf Mar 19 '12 at 23:59

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer
    
Thank you very much that makes alot of sense! Also thanks for all the useful links. –  Alex Kite Mar 20 '12 at 11:07

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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