Show that if $\gcd(m,n)$ divides $c-d$ then $\exists z \in\mathbb Z$ satisfying the pair of congruences (below).

Question

Let $m,n \in\mathbb Z^+$ and $c,d \in\mathbb Z$. Prove that there exists $z\in\mathbb Z$ satisfying the pair of congruences: \begin{eqnarray} 
z \equiv c \bmod m \\ z \equiv d \bmod n 
 \end{eqnarray} iff $\gcd(m, n)$ divides $c − d$. 


I know because it is an iff statement we need to prove a) if $ \exists z \in Z$ satisfying the pair of congruences then $gcd(m,n)$ divides $(c-d)$ b) If $gcd(m,n)$ divides $(c-d)$ then $\exists z \in Z$ satisfying the pair of congruences. I have proved part $a$ already as follows: We know that $m|(z-c)$ and $n|(z-d)$ and therefore $mx=z-c$ and $ny=z-d$ for some $x,y \in Z$.

We can therefore rewrite $z=mx+c = ny+d$ and $c-d = mx-ny$. Notice that from this we can apply Bezout’s Identity. The Identity tells us that $\exists$ such $x, y \in Z$ iff $gcd(m, -n) | (c-d)$. We know that $gcd(m,-n) = gcd(m,n)$. Therefore we have shown that if $ \exists z \in Z$ satisfying the pair of congruences then $gcd(m,n)| (c-d)$.

Next we have to show that if $gcd(m,n)$ divides $(c-d)$ then $\exists z \in Z$ satisfying the pair of congruences.

I am unsure how to prove this part, any suggestions?

Answer 1

Say $gcd(m,n)=a$
So we can say that $m=ak$ and $n=al$ where $gcd(k,l)=1$
So we have from above that there exists integers $x,y$ such that $kx+ly=1$

Now it is given that $a\big|c-d \Rightarrow c-d=ar$
Working from above, we get $krx+lry=r$
So, we get that $c-d=a(krx+lry)=r(mx+ny)=m\alpha + n\beta$
Hence we get that $-m\alpha+c= n\beta+d \Rightarrow m\gamma + c =n\beta + d =z$(say) such that $z \in \mathbb{Z}$

Where $\alpha=rx, \beta=ry, \gamma=-\alpha=-rx$
Thus you get the conditions: $$z\equiv c (mod \,\ m)$$ $$z\equiv d (mod \,\ n)$$