I am stuck with the following problem.

Prove that if $ \gcd(m, n) = 1$, then the pair of congruence $x\equiv a\pmod m$ and $x\equiv b\pmod n$ has a solution for any choice of $a$ and $b$.

Please help.

Regards Rahul

  • $\begingroup$ Just rewrite one of the congruences by using the definition of a congruence and substitute it into the other congruence. Its a direct application of the chinese remainder theorem. So if have practiced with it this proof should proceed nicely. $\endgroup$
    – user60887
    Sep 16 '13 at 3:45
  • $\begingroup$ Yeah..I will try that..Thanks for your help. $\endgroup$
    – TheNoob
    Sep 16 '13 at 16:15

This is called the Chinese remainder theorem. It can be generalized to congruence systems with a higher number of congruence equations where the moduli are pairwise prime.

The proof is as follows:

Let $M_1 = n$ and let $M_2 = m$. then because $(M_1,m)=(n,m)=1$ we see that $M_1$ has an inverse, i.e, there exists an element $M_1^*$ such that $M_1^*.M_1 \equiv 1 \pmod{m}$. The same argument shows that there exists an inverse for $M_2$ and we write it as $M_2^*$ in $\mod{n}$.

Now let's set $x= a.M_1.M_1^* + b.M_2.M_2^*$. See what happens:

$x \equiv a.M_1.M_1^* + b.M_2.M_2^* \equiv a.1 + b.0 \equiv a \pmod{m}$ $x \equiv a.M_1.M_1^* + b.M_2.M_2^* \equiv a.0 + b.1 \equiv b \pmod{n}$.

Because $m \mid M_2 \iff M_2 \equiv 0 \pmod{m}$ and $n \mid M_1 \iff M_1 \equiv 0 \pmod{n}$, and also $M_1^*.M_1 \equiv 1 \pmod{m}$ and $M_2^*.M_2 \equiv 1 \pmod{n}$.

You can generalize it to a system of congruences with more equations. If you're given the system $x \equiv a_1 \pmod{m_1}$ $\cdots$ $x \equiv a_n \pmod{m_n}$ where $(m_i,m_j)=1$ for any $i \neq j$ you could solve it by setting $\displaystyle M_i = \frac{m_1.m_2.\cdots.m_n}{m_i}$ and follow the same argument.


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.