# Relatively Prime Mods and CRT

I have to show that the system of congruences

$$\begin{cases} x\equiv a\pmod m\\ x\equiv b\pmod n \end{cases}$$

has solutions for any a,b integers iff $\gcd(m,n)=1$ where m,n are integers.

So far I have gotten this far...

$mk + a = nl + b$ for $k,l$ integers

$a - b = nl - mk$

$\gcd(m,n)$ divides m and n by definition so it divides a linear combination of them

therefore, $\gcd(m,n)|(a - b)$

I don't know where to go from here to show that it has solutions iff the $\gcd(m,n) = 1$ (they are relatively prime)

You've got that $\gcd(m,n)|(a-b)$. But for this to be true for all integers $a$ and $b$, we need to have $\gcd(m,n)=1$ (just take for example $a_1-b_1=2$ and $a_2-b_2=3$). So, we've shown that if the system has a solution $\forall a,b\in\mathbb{Z}$, it implies that $\gcd(m,n)=1$.