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?

  • $\begingroup$ 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$. $\endgroup$ – Hurkyl Dec 2 '13 at 23:18

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.