中国剰余定理（孫子、秦九韶）

存在性、ステップ1（部品を作る）：各 $i$ について $M_i=M/m_i$（$m_i$ を除くすべての法の積）を定義する。$m_j$ 同士は互いに素なので、$m_i$ のどの素因数も他の $m_j$（$j\neq i$）には現れず、したがって $\gcd(M_i,m_i)=1$ である。ベズーの等式（拡張ユークリッドの互除法）により、$M_i$ の法 $m_i$ における逆元となる整数 $y_i$ が存在し、$M_iy_i\equiv1\pmod{m_i}$ を満たす。

存在性、ステップ2（解を組み立てる）：$x=\sum_{i=1}^{k}a_iM_iy_i\bmod M$ と定める。任意の添字 $i$ を固定し、この和を法 $m_i$ で簡約する。$j\neq i$ のすべてについて、$M_j=M/m_j$ は（$i\neq j$ であるから）因数として $m_i$ を含むので $m_i\mid M_j$ であり、項 $a_jM_jy_j\equiv0\pmod{m_i}$ となる。残るのは第 $i$ 項のみ：$M_iy_i\equiv1\pmod{m_i}$ を用いて $x\equiv a_iM_iy_i\equiv a_i\cdot1=a_i\pmod{m_i}$。$i$ は任意だったので、$x$ はすべての合同式 $x\equiv a_i\pmod{m_i}$ を同時に満たす。

法 $M$ での一意性：$x\equiv a_i\pmod{m_i}$ をすべて満たす別の整数 $x'$ があるとする。このとき、すべての $i$ について $x-x'\equiv0\pmod{m_i}$、すなわちすべての $m_i$ が $x-x'$ を割り切る。$m_i$ 同士は互いに素なので、それらの最小公倍数は積 $M$ に等しく、したがって $M\mid(x-x')$ — 互いに素な数の公倍数は、それらの積の倍数でなければならない。ゆえに $x\equiv x'\pmod M$：解は法 $M$ のもとで一意であり、主張の通りである。

小さな例での検証：$m_1=3,m_2=5$、$a_1=2,a_2=3$、すなわち連立系 $x\equiv2\pmod3,\ x\equiv3\pmod5$ を取る。ここで $M=15$；$M_1=5$ は $5y_1\equiv1\pmod3$、すなわち $2y_1\equiv1\pmod3$ を要求するので $y_1=2$；$M_2=3$ は $3y_2\equiv1\pmod5$ を要求するので $y_2=2$。すると $x=2\cdot5\cdot2+3\cdot3\cdot2=20+18=38\equiv8\pmod{15}$、すなわち $x=8$。検証：$8=2\cdot3+2$ は法 $3$ で余り $2$、$8=1\cdot5+3$ は法 $5$ で余り $3$ — 両方の合同式が成り立ち、構成が確認される。