Let integer $x$ satisfy both the following congruences:
$x ≡ a \pmod m$
$x ≡ b \pmod n$
Show that there is a solution to this system if and only if $\gcd (m, n) \mid (a− b$).
We're given $x ≡ a \pmod m$ and $x ≡ b \pmod n$, which means for some integers $p,q$
$$ x = a - pm $$
$$ x = b + qn $$
Equating, we have
$$ qn + pm = a - b $$
By Proposition (1.17) this has integer solutions for $p,q$ if and only if $gcd(n,m) \mid (a-b)$.