Chinese Remainder Theorem (Sunzi, Qin Jiushao)

Existence, step 1 (build the pieces): for each $i$ define $M_i=M/m_i$, the product of all moduli except $m_i$. Because the $m_j$ are pairwise coprime, every prime factor of $m_i$ is absent from every $m_j$ ($j\neq i$), so $\gcd(M_i,m_i)=1$. By Bezout's identity (extended Euclidean algorithm) there exists an integer $y_i$ — the modular inverse of $M_i$ mod $m_i$ — with $M_iy_i\equiv1\pmod{m_i}$.

Existence, step 2 (assemble the solution): set $x=\sum_{i=1}^{k}a_iM_iy_i\bmod M$. Fix any index $i$ and reduce this sum mod $m_i$. For every $j\neq i$, the factor $M_j=M/m_j$ contains $m_i$ as one of its factors (since $i\neq j$), so $m_i\mid M_j$ and the term $a_jM_jy_j\equiv0\pmod{m_i}$. Only the $i$-th term survives: $x\equiv a_iM_iy_i\equiv a_i\cdot1=a_i\pmod{m_i}$ (using $M_iy_i\equiv1\pmod{m_i}$). Since $i$ was arbitrary, $x$ satisfies every congruence $x\equiv a_i\pmod{m_i}$ at once.

Uniqueness mod $M$: suppose $x'$ is another integer satisfying every $x\equiv a_i\pmod{m_i}$. Then $x-x'\equiv0\pmod{m_i}$ for every $i$, i.e. every $m_i$ divides $x-x'$. Because the $m_i$ are pairwise coprime, their least common multiple equals their product $M$, so $M\mid(x-x')$ as well — any common multiple of pairwise-coprime numbers must already be a multiple of their product. Hence $x\equiv x'\pmod M$: the solution is unique modulo $M$, exactly as claimed.

Toy verification: take $m_1=3,m_2=5$ with $a_1=2,a_2=3$, i.e. the system $x\equiv2\pmod3,\ x\equiv3\pmod5$. Here $M=15$; $M_1=5$ needs $5y_1\equiv1\pmod3$, i.e. $2y_1\equiv1\pmod3$, so $y_1=2$; $M_2=3$ needs $3y_2\equiv1\pmod5$, so $y_2=2$. Then $x=2\cdot5\cdot2+3\cdot3\cdot2=20+18=38\equiv8\pmod{15}$, so $x=8$. Check: $8=2\cdot3+2$ leaves remainder $2$ mod $3$, and $8=1\cdot5+3$ leaves remainder $3$ mod $5$ — both congruences hold, confirming the construction.