0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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)$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.