Suppose that $a \equiv b\mod m$ and that $a \equiv b\mod n $ .Assuming gcd$(m;n) = 1 $ ,prove that $a \equiv b\mod mn$

Question

How should I approach this question? I was thinking of splitting it up such as as $ mt=b$ and $ax + ny=b$

Answer 1

Note that $a\equiv b \mod m \implies\color{#d05}{a = mk+b} \,.$ Since $a\equiv b\mod n$ , we have :

$$mk+b\equiv b\mod n \implies mk \equiv 0\mod n$$

Since gcd$(m,n) =1$ , we conclude that $k \equiv 0\mod n \implies \color{#3ce}{k =nl}\,.$

Putting this in the original equation , we get $$a = mnl + b \implies \boxed{\color{#2d0}{a\equiv b\mod mn}}$$

Answer 2

$ a \equiv b \mod m $ means $m |(a-b)$

if $ m | (a-b)$ and $n | (a - b)$ then $lcm(m,n)|(a-b)$

since $lcm(m,n)gcd(m,n) = mn$ and $gcd(m,n) = 1$, we have $lcm(m,n) = mn$

so $mn | (a-b)$