Định lý phần dư Trung Hoa (tồn tại và duy nhất)

Trước hết ta chứng minh trường hợp hai môđun ($k=2$) rồi mở rộng bằng quy nạp. Vì $\gcd(m_1,m_2)=1$, đẳng thức Bézout cho các số nguyên $u,v$ với $m_1 u + m_2 v = 1$. Đặt $x_0 = a_1 m_2 v + a_2 m_1 u$.

Kiểm tra theo môđun $m_1$: từ $m_1 u + m_2 v = 1$ ta có $m_2 v = 1 - m_1 u \equiv 1 \pmod{m_1}$, còn $m_1 u \equiv 0 \pmod{m_1}$, nên $x_0 \equiv a_1\cdot 1 + a_2\cdot 0 = a_1 \pmod{m_1}$.

Đối xứng, theo môđun $m_2$: $m_1 u = 1-m_2 v \equiv 1 \pmod{m_2}$ và $m_2 v \equiv 0 \pmod{m_2}$, nên $x_0 \equiv a_1\cdot 0 + a_2\cdot 1 = a_2 \pmod{m_2}$. Điều này chứng minh sự tồn tại với $k=2$.

Về tính duy nhất khi $k=2$: nếu $x$ và $x'$ cùng giải hệ, thì $x-x'\equiv0\pmod{m_1}$ và $x-x'\equiv0\pmod{m_2}$, tức cả $m_1$ và $m_2$ đều chia hết $d=x-x'$. Nhân phương trình Bézout $m_1 u+m_2 v=1$ với $d$: $d = d m_1 u + d m_2 v$. Vì $m_2\mid d$, số hạng đầu $d m_1 u$ là bội của $m_1 m_2$; vì $m_1\mid d$, số hạng thứ hai $d m_2 v$ cũng là bội của $m_1 m_2$. Do đó $m_1 m_2 \mid d$, tức $x\equiv x'\pmod{m_1 m_2}$.

Với $k>2$ tổng quát, quy nạp: hai đồng dư đầu tương đương (theo trường hợp $k=2$) với một đồng dư duy nhất theo môđun $m_1 m_2$; vì $m_3$ nguyên tố cùng nhau với cả $m_1$ và $m_2$, nó nguyên tố cùng nhau với tích $m_1 m_2$ của chúng, nên ta lại ghép tiếp được, cứ thế tới $k$. Cũng chú ý rằng tổng tường minh $x \equiv \sum_{i=1}^{k} a_i M_i y_i \pmod{M}$ hoạt động trực tiếp cho mọi $k$ bằng đúng lập luận đó: $M_i = M/m_i$ nguyên tố cùng nhau với $m_i$ nên nghịch đảo $y_i$ tồn tại, và mọi số hạng $j\neq i$ đều chứa $m_i$ làm thừa số của $M_j$. $\blacksquare$