Định lý phần dư Trung Hoa (Tôn Tử, Tần Cửu Thiều)

Sự tồn tại, bước 1 (dựng các mảnh ghép): với mỗi $i$, định nghĩa $M_i=M/m_i$, tích của mọi modulo trừ $m_i$. Vì các $m_j$ đôi một nguyên tố cùng nhau, mọi thừa số nguyên tố của $m_i$ không xuất hiện trong bất kỳ $m_j$ nào ($j\neq i$), nên $\gcd(M_i,m_i)=1$. Theo đẳng thức Bezout (thuật toán Euclid mở rộng), tồn tại số nguyên $y_i$ — nghịch đảo modulo của $M_i$ theo $m_i$ — sao cho $M_iy_i\equiv1\pmod{m_i}$.

Sự tồn tại, bước 2 (ráp nghiệm): đặt $x=\sum_{i=1}^{k}a_iM_iy_i\bmod M$. Cố định một chỉ số $i$ bất kỳ rồi rút gọn tổng này theo modulo $m_i$. Với mọi $j\neq i$, thừa số $M_j=M/m_j$ chứa $m_i$ như một trong các thừa số của nó (vì $i\neq j$), nên $m_i\mid M_j$ và số hạng $a_jM_jy_j\equiv0\pmod{m_i}$. Chỉ số hạng thứ $i$ còn lại: $x\equiv a_iM_iy_i\equiv a_i\cdot1=a_i\pmod{m_i}$ (dùng $M_iy_i\equiv1\pmod{m_i}$). Vì $i$ tùy ý, $x$ thỏa mãn mọi đồng dư $x\equiv a_i\pmod{m_i}$ cùng lúc.

Tính duy nhất theo modulo $M$: giả sử $x'$ là một số nguyên khác cũng thỏa mọi $x\equiv a_i\pmod{m_i}$. Khi đó $x-x'\equiv0\pmod{m_i}$ với mọi $i$, nghĩa là mọi $m_i$ đều chia hết $x-x'$. Vì các $m_i$ đôi một nguyên tố cùng nhau, bội chung nhỏ nhất của chúng bằng tích $M$ của chúng, nên $M\mid(x-x')$ — bất kỳ bội chung nào của các số đôi một nguyên tố cùng nhau đều phải là bội của tích chúng. Vậy $x\equiv x'\pmod M$: nghiệm là duy nhất theo modulo $M$, đúng như khẳng định.

Kiểm tra với ví dụ nhỏ: lấy $m_1=3,m_2=5$ với $a_1=2,a_2=3$, tức hệ $x\equiv2\pmod3,\ x\equiv3\pmod5$. Ở đây $M=15$; $M_1=5$ cần $5y_1\equiv1\pmod3$, tức $2y_1\equiv1\pmod3$, nên $y_1=2$; $M_2=3$ cần $3y_2\equiv1\pmod5$, nên $y_2=2$. Khi đó $x=2\cdot5\cdot2+3\cdot3\cdot2=20+18=38\equiv8\pmod{15}$, nên $x=8$. Kiểm tra: $8=2\cdot3+2$ dư $2$ theo modulo $3$, và $8=1\cdot5+3$ dư $3$ theo modulo $5$ — cả hai đồng dư đều đúng, xác nhận cách dựng.