Suppose that $(a,m)=1$ and $(b,n)=1$, where $(x,y)$ denotes the greatest common divisor of $x$ and $y$. Show that if $$ c \equiv a \pmod{m} \\ c \equiv b \pmod{n} \\ $$ then $(c,mn)=1$.
I've tried to make this connection but the solution is eluding me.
On
I just came up with another way to show this. Since $(a,m)=1$ there are integers $r$ and $s$ such that $ar + ms = 1$ (Bezout's Identity). We then have $$ c \equiv a \pmod{m} \\ cr \equiv ar \pmod{m} \\ cr \equiv 1 - ms \pmod{m} \\ cr \equiv 1 \pmod{m} \\ $$ Therefore there is a $p$ such that $cr = 1 + pm$ so $cr - pm =1$, which means that $(c,m)=1$. A similar argument shows that $(c,n)=1$. Therefore it is also true that $(c,mn)=1$. Is my logic correct?
Suppose to the contrary that $(c,mn)\gt 1$. Then there is a prime $p$ that divides $c$ amd $mn$.
Since $p$ divides $mn$, it divides at least one of $m$ or $n$, say $m$.
Since $c\equiv a\pmod{m}$, $c=a+qm$ for some $q$. It $p$ divides $m$ and $c$, then $p$ divides $a$.
Thus $p$ divides $a$ and $m$, contradicting the fact that $(a,m)=1$.