Solution for a pair of congruences. 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
 A: 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.
