[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.[/step]

[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: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]