system of congruences has a solution if GCD = 1

Question

I have the following problem.

Let m, n be arbitrary non zero integers. Show that $x ≡ a \pmod m$ $x ≡ b\pmod n$ has a solution if $\gcd(m, n)$ divides both $a$ and $b$.

Also interested in the converse.

I've tried messing around with various thing, including bezout's identity, and euler's function, but haven't really made much progress. Have also tried some group theory but I really don't have a solid basis in that.

Answer 1

Hint:

Set $d=\gcd(m,n)$. Show the congruences imply a solution is divisible by $d$. So set $$x=yd,\quad m=m'd,\quad n=n'd,\quad a=da',\quad b=db'.$$ Note that $m'$ and $n'$ are coprime and the system of congruences can be rewritten as \begin{cases} y\equiv a'\pmod{m'},\\ y\equiv b'\pmod{n'}. \end{cases}

The converse is not true. What is true uis that the system of congruences has a solution if and only if $a\equiv b\mod\gcd(m,n)$ (this condition is of course satisfied with your hypotheses.

Answer 2

Your problem is a partial conclusion of Chinese Remainder Theorem (https://en.wikipedia.org/wiki/Chinese_remainder_theorem) and the direct side is correct. For the converse notice the following counter example$$x\equiv5\pmod{2}\\x\equiv3\pmod{4}$$which has the answer $x=15$ but $$\gcd(2,4)=2\nmid \quad3,5$$