[proofplan]
We translate each congruence into a divisibility statement. Necessity follows by observing that any common solution makes both $x-a$ and $x-b$ divisible by the corresponding moduli, so their difference is divisible by the greatest common divisor. For sufficiency, we divide out $d=\gcd(m,n)$, use Bézout's identity for the coprime quotients, and construct a correction term $mk$ that moves $a$ into the desired residue class modulo $n$. Finally, we prove that the common period of the two congruences is exactly $\operatorname{lcm}(m,n)$.
[/proofplan]
[step:Derive the compatibility condition from a common solution]
Assume that $x \in \mathbb{Z}$ satisfies
\begin{align*}
x \equiv a \pmod{m}
\end{align*}
and
\begin{align*}
x \equiv b \pmod{n}.
\end{align*}
By the divisibility definition of congruence, there exist integers $r,s \in \mathbb{Z}$ such that
\begin{align*}
x-a = mr
\end{align*}
and
\begin{align*}
x-b = ns.
\end{align*}
Let
\begin{align*}
d := \gcd(m,n).
\end{align*}
Since $d \mid m$ and $d \mid n$, we have $d \mid (x-a)$ and $d \mid (x-b)$. Therefore $d$ divides their difference:
\begin{align*}
a-b = (x-b)-(x-a).
\end{align*}
Thus
\begin{align*}
a \equiv b \pmod{d},
\end{align*}
which is the required compatibility condition.
[/step]
[step:Construct a solution from the compatibility condition]
Assume now that
\begin{align*}
a \equiv b \pmod{\gcd(m,n)}.
\end{align*}
Set
\begin{align*}
d := \gcd(m,n).
\end{align*}
Since $d \mid (b-a)$, choose $t \in \mathbb{Z}$ such that
\begin{align*}
b-a = dt.
\end{align*}
Define the coprime quotients $M,N \in \mathbb{Z}$ by
\begin{align*}
M := \frac{m}{d}
\end{align*}
and
\begin{align*}
N := \frac{n}{d}.
\end{align*}
Then $M>0$, $N>0$, and $\gcd(M,N)=1$. By Bézout's identity, choose $u,v \in \mathbb{Z}$ such that
\begin{align*}
uM+vN=1.
\end{align*}
Define
\begin{align*}
k := ut
\end{align*}
and
\begin{align*}
x_0 := a+mk.
\end{align*}
Then $x_0-a=mk$, so
\begin{align*}
x_0 \equiv a \pmod{m}.
\end{align*}
It remains to check the congruence modulo $n$. Since $m=dM$ and $b-a=dt$, we compute
\begin{align*}
x_0-b = a+mk-b = dMk-dt = d(Mk-t).
\end{align*}
Using $k=ut$ and $uM+vN=1$, we get
\begin{align*}
Mk-t = Mut-t = t(uM-1) = -tvN.
\end{align*}
Hence
\begin{align*}
x_0-b = d(-tvN)=n(-tv),
\end{align*}
so $n \mid (x_0-b)$. Therefore
\begin{align*}
x_0 \equiv b \pmod{n}.
\end{align*}
Thus $x_0$ is a solution.
[guided]
We need to build an integer $x_0$ satisfying both congruences. The first congruence suggests starting with $a$ and adding a multiple of $m$, so we look for a solution of the form
\begin{align*}
x_0 := a+mk
\end{align*}
for some $k \in \mathbb{Z}$. This automatically gives
\begin{align*}
x_0 \equiv a \pmod{m}.
\end{align*}
The remaining problem is to choose $k$ so that $x_0 \equiv b \pmod{n}$.
Let
\begin{align*}
d := \gcd(m,n).
\end{align*}
The compatibility hypothesis says $d \mid (b-a)$, so there exists $t \in \mathbb{Z}$ with
\begin{align*}
b-a = dt.
\end{align*}
Now define
\begin{align*}
M := \frac{m}{d}
\end{align*}
and
\begin{align*}
N := \frac{n}{d}.
\end{align*}
Then $m=dM$, $n=dN$, and $\gcd(M,N)=1$, because all common factors of $m$ and $n$ have already been removed by dividing by $d$.
The congruence $a+mk \equiv b \pmod{n}$ is equivalent to $n \mid (a+mk-b)$. Substituting $m=dM$, $n=dN$, and $b-a=dt$, this condition becomes
\begin{align*}
dN \mid d(Mk-t).
\end{align*}
Since $N$ is an integer and $d>0$, it is enough to arrange
\begin{align*}
N \mid (Mk-t).
\end{align*}
Thus we need to solve
\begin{align*}
Mk \equiv t \pmod{N}.
\end{align*}
Because $\gcd(M,N)=1$, Bézout's identity gives integers $u,v \in \mathbb{Z}$ such that
\begin{align*}
uM+vN=1.
\end{align*}
This means that $uM \equiv 1 \pmod{N}$, so multiplying by $t$ gives
\begin{align*}
Mut \equiv t \pmod{N}.
\end{align*}
Therefore choose
\begin{align*}
k := ut.
\end{align*}
Then
\begin{align*}
Mk-t = Mut-t = t(uM-1) = -tvN,
\end{align*}
so $N \mid (Mk-t)$. Consequently
\begin{align*}
x_0-b = a+m k-b = d(Mk-t)
\end{align*}
is divisible by $dN=n$. Hence
\begin{align*}
x_0 \equiv b \pmod{n}.
\end{align*}
Since $x_0=a+mk$, we also have
\begin{align*}
x_0 \equiv a \pmod{m}.
\end{align*}
Thus $x_0$ is a simultaneous solution.
[/guided]
[/step]
[step:Show that any two solutions differ by a multiple of the least common multiple]
Let $y,z \in \mathbb{Z}$ be two solutions. Then
\begin{align*}
y \equiv z \pmod{m}
\end{align*}
because both are congruent to $a$ modulo $m$, and
\begin{align*}
y \equiv z \pmod{n}
\end{align*}
because both are congruent to $b$ modulo $n$. Hence there exist $r,s \in \mathbb{Z}$ such that
\begin{align*}
y-z = mr
\end{align*}
and
\begin{align*}
y-z = ns.
\end{align*}
Let $d=\gcd(m,n)$, $M=m/d$, and $N=n/d$. Then $\gcd(M,N)=1$, and
\begin{align*}
\operatorname{lcm}(m,n)=dMN.
\end{align*}
From $y-z=mr=dMr$ and $n=dN \mid (y-z)=dMr$, we get $N \mid Mr$. Since $\gcd(M,N)=1$, Euclid's lemma gives $N \mid r$. Thus $r=Nq$ for some $q \in \mathbb{Z}$. Therefore
\begin{align*}
y-z = mNq = dMNq = \operatorname{lcm}(m,n)q.
\end{align*}
So
\begin{align*}
y \equiv z \pmod{\operatorname{lcm}(m,n)}.
\end{align*}
[/step]
[step:Verify that adding a multiple of the least common multiple preserves both congruences]
Let $x_0 \in \mathbb{Z}$ be a solution, and let $q \in \mathbb{Z}$. Define
\begin{align*}
x := x_0+q\operatorname{lcm}(m,n).
\end{align*}
Since $m \mid \operatorname{lcm}(m,n)$ and $n \mid \operatorname{lcm}(m,n)$, we have
\begin{align*}
m \mid (x-x_0)
\end{align*}
and
\begin{align*}
n \mid (x-x_0).
\end{align*}
Because $x_0 \equiv a \pmod{m}$ and $x_0 \equiv b \pmod{n}$, it follows from the transitivity of congruence [citetheorem:9332] that
\begin{align*}
x \equiv a \pmod{m}
\end{align*}
and
\begin{align*}
x \equiv b \pmod{n}.
\end{align*}
Thus every integer congruent to $x_0$ modulo $\operatorname{lcm}(m,n)$ is again a solution.
Conversely, the previous step proves that every solution is congruent to $x_0$ modulo $\operatorname{lcm}(m,n)$. Hence the full solution set is precisely the single residue class
\begin{align*}
\{x \in \mathbb{Z}: x \equiv x_0 \pmod{\operatorname{lcm}(m,n)}\}.
\end{align*}
This proves the stated description of all solutions and completes the proof.
[/step]
