I have to show that the system of congruences

$$ \begin{cases} x\equiv a\pmod m\\ x\equiv b\pmod n \end{cases} $$

has solutions for any a,b integers iff $\gcd(m,n)=1$ where m,n are integers.

So far I have gotten this far...

$mk + a = nl + b$ for $k,l$ integers

$a - b = nl - mk$

$\gcd(m,n)$ divides m and n by definition so it divides a linear combination of them

therefore, $\gcd(m,n)|(a - b)$

I don't know where to go from here to show that it has solutions iff the $\gcd(m,n) = 1$ (they are relatively prime)


You've got that $\gcd(m,n)|(a-b)$. But for this to be true for all integers $a$ and $b$, we need to have $\gcd(m,n)=1$ (just take for example $a_1-b_1=2$ and $a_2-b_2=3$). So, we've shown that if the system has a solution $\forall a,b\in\mathbb{Z}$, it implies that $\gcd(m,n)=1$.

For the converse we just need to apply the Chinese Remainder Theorem.

  • $\begingroup$ Well, the OP wants to prove CRT. $\endgroup$ – Pedro Tamaroff Oct 30 '13 at 0:07
  • $\begingroup$ The proof can be seen on the link. $\endgroup$ – Mateus Sampaio Oct 30 '13 at 0:08
  • $\begingroup$ Perfect! thanks so much Mateus Sampaio. The only number that divides all other numbers is 1 so the gcd must be 1 and the mods must be relatively prime. $\endgroup$ – user1874239 Oct 30 '13 at 0:09

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.