Consider the system of Congruences $x \equiv a \pmod{m}$ and $x \equiv b \pmod{n}$

Question

I want to prove that this system has a unique solution $\pmod{\frac{mn}{g}}$, where $g= \gcd(m,n)$ provided that $g \mid b-a$

Here is my attempt.

From $x \equiv a \pmod{m}$ we know that $m \mid x-a$ and so there must exists an integer $k$ such that $mk = x-a$ and so $x = mk + a$. Now we substitute this equation for $x$ into the $2^{nd}$ congruence to get $mk + a \equiv b \pmod{n}$ which implies that $mk \equiv b-a \pmod{n}$ and so there must exists an integer $q$ such that $nq = mk -(b-a)$ and so $mk-nq = b-a$, we let $q' = -q$ so we now have $mk + nq' = b$ which is a diophantine equation. But I am suck here and I can't show that there is a unique solution $\pmod{\frac{mn}{g}}$ any suggestion ?

Answer 1

First off, there may not even be a solution. Take for example, $m=n, a=0, b=1$. Then there is no solution to $x \equiv 0$ and $x \equiv 1$ (mod $n$). You can check that there is a solution if and only if $a \equiv b$ (mod $g$). The only if is just the fact that $x \equiv a$ (mod $m$) implies $x \equiv a$ (mod $k$) for any $k \vert m$.

To find a solution, factor $m=m_1 g$ and $n=n_1 g$ so $gcd(m_1,n_1)=1$. By assumption $a=b+kg$ for some $k$. We want to find $l$ so that $x=a+lm \equiv b$ (mod $n$). This is equivalent to:

$a+lm =b+kg+l m_1 g \equiv b$ (mod $n$) so $kg+l m_1 g \equiv 0$ (mod $n_1 g$). This is the same as (check this) solving $k+l m_1 \equiv 0$ (mod $n_1 $) (dividing out $g$).But $gcd(m_1,n_1)=1$ so we can invert $m_1$ and find a solution.

If you know the Chinese Remainder Theorem, there is a quicker proof of existence by considering the (highest) prime powers of $m,n,g$ and $lcm(m,n)$ and the assumption $a \equiv b$ (mod $g$).

For uniqueness, suppose there are two solutions, $x$ and $y$. Then $x \equiv a \equiv y$ (mod $m$) and $x \equiv b \equiv y$ (mod $n$). So $m \vert (x-y)$ and $n \vert (x-y)$ so $lcm(m,n)=\frac{mn}{g} \vert (x-y)$, i.e. $x \equiv y$ (mod $\frac{mn}{g}$).

Answer 2

This is indeed one of the formulations of the Chinese remainder theorem (CRT), for the case of two congruences (check under the link the case "even if the $n_i$ are not pairwise coprime").

You can reduce easily to the classical formulation of the CRT, which says a unique solution exists modulo the product of the moduli provided the moduli are relatively prime. Note that you suppose $a\equiv b\pmod g$, and since you are only interested in the unique existence of a solution, you might as well subtract the common remainder $a\bmod g=b\bmod g$ from $a$ and $b$ in your problem (this changes the solutions for $x$, which hare also decreased, but not their existence or uniqueness).

But after this subtraction, $g$ divides everything (that is $a,b,m,n$), and you can obtain an equivalent system of equations $x/g\equiv a/g\pmod{m/g}$, $x/g\equiv b/g\pmod{b/g}$, or calling $x'=x/g$: $$ \begin{align} x'&\equiv a/g\pmod{m/g},\\ x'&\equiv b/g\pmod{b/g}. \end{align} $$ But the new moduli are relatively prime: $\gcd(m/g,n/g)=\gcd(m,n)/g=1$, so now the classical CRT applies and gives a unique solution for $x'$ modulo $(m/g)(n/g)=mn/g^2$. The solution for $x=gx'$ is then unique modulo $mn/g=\operatorname{lcm}(m,n)$