[proofplan] Use [Bézout's identity](/theorems/727) to construct two integer weights $tn$ and $sm$ that behave like complementary idempotents modulo $m$ and modulo $n$. The linear combination $x = a(tn) + b(sm)$ is then forced to reduce to $a$ modulo $m$ and to $b$ modulo $n$. For uniqueness, compare any two solutions and use the same Bézout relation to show that divisibility by both coprime moduli implies divisibility by their product. [/proofplan] [step:Construct a simultaneous solution using Bézout coefficients] Since $m,n \in \mathbb{N}$ and $\gcd(m,n)=1$, the hypotheses of GCD as Linear Combination apply. Hence there exist integers $s,t \in \mathbb{Z}$ such that \begin{align*} sm + tn = 1. \end{align*} Define the integer $x \in \mathbb{Z}$ by \begin{align*} x = a(tn) + b(sm). \end{align*} Modulo $m$, the identity $tn = 1 - sm$ gives $tn \equiv 1 \pmod{m}$, while $sm \equiv 0 \pmod{m}$. Therefore \begin{align*} x &= a(tn) + b(sm) \\ &\equiv a \cdot 1 + b \cdot 0 \pmod{m} \\ &\equiv a \pmod{m}. \end{align*} Modulo $n$, the identity $sm = 1 - tn$ gives $sm \equiv 1 \pmod{n}$, while $tn \equiv 0 \pmod{n}$. Hence \begin{align*} x &= a(tn) + b(sm) \\ &\equiv a \cdot 0 + b \cdot 1 \pmod{n} \\ &\equiv b \pmod{n}. \end{align*} Thus $x$ satisfies both congruences. [guided] The construction starts from the coprimality hypothesis. Since $m,n \in \mathbb{N}$ and $\gcd(m,n)=1$, GCD as Linear Combination gives integers $s,t \in \mathbb{Z}$ satisfying \begin{align*} sm + tn = 1. \end{align*} The purpose of this identity is to create two integer factors with opposite behaviour modulo the two moduli. Define \begin{align*} x = a(tn) + b(sm). \end{align*} This is an integer because $a,b,s,t,m,n \in \mathbb{Z}$. We first reduce $x$ modulo $m$. From $sm + tn = 1$, we have $tn = 1 - sm$. Since $m$ divides $sm$, this gives \begin{align*} tn \equiv 1 \pmod{m}, \end{align*} and also \begin{align*} sm \equiv 0 \pmod{m}. \end{align*} Substituting these two congruences into the definition of $x$ yields \begin{align*} x &= a(tn) + b(sm) \\ &\equiv a \cdot 1 + b \cdot 0 \pmod{m} \\ &\equiv a \pmod{m}. \end{align*} Now reduce $x$ modulo $n$. The same Bézout identity gives $sm = 1 - tn$. Since $n$ divides $tn$, we obtain \begin{align*} sm \equiv 1 \pmod{n}, \end{align*} and also \begin{align*} tn \equiv 0 \pmod{n}. \end{align*} Using the definition of $x$ again, \begin{align*} x &= a(tn) + b(sm) \\ &\equiv a \cdot 0 + b \cdot 1 \pmod{n} \\ &\equiv b \pmod{n}. \end{align*} Thus the integer $x = a(tn) + b(sm)$ is a simultaneous solution of the two congruences. [/guided] [/step] [step:Show that two simultaneous solutions differ by a multiple of $mn$] Let $y \in \mathbb{Z}$ be another simultaneous solution, so \begin{align*} y &\equiv a \pmod{m}, \\ y &\equiv b \pmod{n}. \end{align*} Since $x$ also satisfies the same congruences, subtracting congruences gives \begin{align*} y - x &\equiv 0 \pmod{m}, \\ y - x &\equiv 0 \pmod{n}. \end{align*} Thus there exist integers $r,q \in \mathbb{Z}$ such that \begin{align*} y - x &= mr, \\ y - x &= nq. \end{align*} Using the Bézout identity $sm + tn = 1$, multiply by $y-x$: \begin{align*} y-x &= (sm+tn)(y-x) \\ &= s m (y-x) + t n (y-x) \\ &= s m (nq) + t n (mr) \\ &= mn(sq + tr). \end{align*} Since $sq+tr \in \mathbb{Z}$, this proves $mn \mid (y-x)$, hence \begin{align*} y \equiv x \pmod{mn}. \end{align*} [guided] Let $y \in \mathbb{Z}$ be any other integer satisfying the same two congruences: \begin{align*} y &\equiv a \pmod{m}, \\ y &\equiv b \pmod{n}. \end{align*} We compare $y$ with the constructed solution $x$. Since $x \equiv a \pmod{m}$ and $y \equiv a \pmod{m}$, subtraction of congruent integers gives \begin{align*} y - x \equiv 0 \pmod{m}. \end{align*} Equivalently, there exists an integer $r \in \mathbb{Z}$ such that \begin{align*} y - x = mr. \end{align*} Similarly, since $x \equiv b \pmod{n}$ and $y \equiv b \pmod{n}$, there exists an integer $q \in \mathbb{Z}$ such that \begin{align*} y - x = nq. \end{align*} The goal is to prove divisibility by $mn$, not just separately by $m$ and by $n$. The coprimality of $m$ and $n$ is used through the same Bézout identity \begin{align*} sm + tn = 1. \end{align*} Multiplying this identity by $y-x$ gives \begin{align*} y-x &= (sm+tn)(y-x) \\ &= s m (y-x) + t n (y-x). \end{align*} Now substitute the two divisibility representations. In the first term use $y-x=nq$, and in the second term use $y-x=mr$: \begin{align*} y-x &= s m (nq) + t n (mr) \\ &= mn(sq + tr). \end{align*} Because $s,q,t,r \in \mathbb{Z}$, the integer $sq+tr$ belongs to $\mathbb{Z}$. Therefore $mn \mid (y-x)$, which is exactly \begin{align*} y \equiv x \pmod{mn}. \end{align*} So any two simultaneous solutions are congruent modulo $mn$. [/guided] [/step] [step:Conclude existence and uniqueness modulo $mn$] The integer \begin{align*} x = a(tn) + b(sm), \end{align*} where $s,t \in \mathbb{Z}$ satisfy $sm+tn=1$, is a simultaneous solution. The previous step shows that every simultaneous solution is congruent to $x$ modulo $mn$. Hence the system has a unique solution modulo $mn$. [/step]