Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

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

share|cite|improve this answer

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?

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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