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!
Best Answer
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.