For coprime positive $m,n$, every pair of residue classes modulo $m$ and $n$ has a unique simultaneous class modulo $mn$

If $x$ solves both congruences, then $m\mid (x-a)$ and $n\mid (x-b)$. Since $d$ divides $m,n$, it divides both differences and therefore their difference $b-a$; equivalently $d\mid (a-b)$.

Conversely suppose $d\mid (a-b)$ and write $a-b=dc$, $m=d{m}^{\mathrm{\prime }}$, $n=d{n}^{\mathrm{\prime }}$ as in [L2]. Choose $u,v$ with $u{m}^{\mathrm{\prime }}+v{n}^{\mathrm{\prime }}=1$ by [L3], put $t:=-uc$, and set $x:=a+mt$. Then $x\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}m)$, while $x-b=(a-b)+d{m}^{\mathrm{\prime }}t=d(c-m^{\mathrm{\prime }}uc)=dc{n}^{\mathrm{\prime }}v$, so $x\equiv b(\mathrm{m}\mathrm{o}\mathrm{d}n)$.

If $x,y$ are two solutions, then $m\mid (x-y)$, so $x-y=d{m}^{\mathrm{\prime }}q$ for some integer $q$. Also $n=d{n}^{\mathrm{\prime }}\mid (x-y)$, hence cancellation of $d$ gives $n^{\mathrm{\prime }}\mid m^{\mathrm{\prime }}q$; multiplying a Bézout identity for $m^{\mathrm{\prime }},n^{\mathrm{\prime }}$ by $q$ shows $n^{\mathrm{\prime }}\mid q$. Thus $d{m}^{\mathrm{\prime }}{n}^{\mathrm{\prime }}=mn\mathrm{/}d$ divides $x-y$.

Conversely, if $mn\mathrm{/}d=d{m}^{\mathrm{\prime }}{n}^{\mathrm{\prime }}$ divides $x-y$, then both $m=d{m}^{\mathrm{\prime }}$ and $n=d{n}^{\mathrm{\prime }}$ divide $x-y$, so $x$ and $y$ satisfy exactly the same two residue conditions. Hence, when compatible, the solution set is one class modulo $mn\mathrm{/}d$.

When $\gcd (m,n)=1$, one has $d=1$ and the compatibility condition is automatic; the modulus $mn\mathrm{/}d$ is $mn$, so steps 1.1 through 1.4 give the stated bijection between pairs of residue classes and simultaneous classes. The same proof applies when either modulus is $1$.