# Chinese Remainder Theorem with coprime congruences

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.

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$.
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?
• This looks good. A more concise way to do most of the work is "$a$ is invertible modulo $m$, therefore $c$ is invertible modulo $m$, since $a$ and $c$ are the same modulo $m$", assuming you recall that being invertible modulo $m$ is the same as being relatively prime to $m$. – Hurkyl Dec 2 '13 at 23:18