Chinese remainder theorem (existence and uniqueness)

We first prove the two-modulus case ($k=2$) and then extend by induction. Since $\gcd(m_1,m_2)=1$, Bézout's identity gives integers $u,v$ with $m_1 u + m_2 v = 1$. Set $x_0 = a_1 m_2 v + a_2 m_1 u$.

Check modulo $m_1$: from $m_1 u + m_2 v = 1$ we have $m_2 v = 1 - m_1 u \equiv 1 \pmod{m_1}$, while $m_1 u \equiv 0 \pmod{m_1}$, so $x_0 \equiv a_1\cdot 1 + a_2\cdot 0 = a_1 \pmod{m_1}$.

Symmetrically, modulo $m_2$: $m_1 u = 1-m_2 v \equiv 1 \pmod{m_2}$ and $m_2 v \equiv 0 \pmod{m_2}$, so $x_0 \equiv a_1\cdot 0 + a_2\cdot 1 = a_2 \pmod{m_2}$. This proves existence for $k=2$.

For uniqueness when $k=2$: if $x$ and $x'$ both solve the system, then $x-x'\equiv0\pmod{m_1}$ and $x-x'\equiv0\pmod{m_2}$, i.e. both $m_1$ and $m_2$ divide $d=x-x'$. Multiply the Bézout equation $m_1 u+m_2 v=1$ by $d$: $d = d m_1 u + d m_2 v$. Since $m_2\mid d$, the first term $d m_1 u$ is a multiple of $m_1 m_2$; since $m_1\mid d$, the second term $d m_2 v$ is also a multiple of $m_1 m_2$. Hence $m_1 m_2 \mid d$, i.e. $x\equiv x'\pmod{m_1 m_2}$.

For general $k>2$, induction: the first two congruences are equivalent (by the $k=2$ case) to a single congruence modulo $m_1 m_2$; since $m_3$ is coprime to both $m_1$ and $m_2$, it is coprime to their product $m_1 m_2$, so we can combine again, and so on up to $k$. Notice also that the explicit sum $x \equiv \sum_{i=1}^{k} a_i M_i y_i \pmod{M}$ works directly for any $k$ by the exact same reasoning: $M_i = M/m_i$ is coprime to $m_i$ so its inverse $y_i$ exists, and every term $j\neq i$ contains $m_i$ as a factor of $M_j$. $\blacksquare$