Solution for a pair of congruences.

Question

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

Answer 1

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.