Định lý phần dư Trung Hoa

Vì các môđun không có ước nguyên tố chung, điều kiện dư $a_1$ theo $m_1$ và điều kiện dư $a_2$ theo $m_2$ là các ràng buộc hoàn toàn độc lập — giống như chỉ định tọa độ $x$ và tọa độ $y$ của một điểm một cách tách biệt. Đẳng thức Bézout cho ta các "vectơ cơ sở" bằng $1$ theo một môđun và bằng $0$ theo mọi môđun khác, cho phép dựng nghiệm trực tiếp như một tổ hợp tuyến tính.

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$

Đây là ý nghĩa cấu trúc của CRT: số học theo môđun $m_1 m_2$ theo đúng nghĩa đen chính là hai bản sao độc lập của số học modulo (một theo $m_1$, một theo $m_2$) chạy song song. Đó vừa là lý do hàm phi Euler $\varphi$ tách nhân gọn gàng trên các số nguyên tố cùng nhau, vừa là lý do máy tính có thể tăng tốc các phép tính số nguyên lớn và mật mã bằng cách thực hiện riêng trên từng thành phần nhỏ.

Thứ nhất, $\psi$ xác định tốt: nếu $x\equiv x'\pmod{m_1 m_2}$ thì $m_1 m_2\mid(x-x')$, nên cả $m_1$ và $m_2$ đều chia hết $x-x'$, nghĩa là $x\equiv x'\pmod{m_1}$ và $x\equiv x'\pmod{m_2}$.

Thứ hai, $\psi$ bảo toàn phép cộng và phép nhân ở từng tọa độ vì phép rút gọn theo môđun $m_i$ bảo toàn chúng (đã chứng minh ở chủ đề đầu về đồng dư), nên $\psi$ là một đồng cấu vành.

Thứ ba, Định lý 1 ở trên nói chính xác rằng với mỗi cặp $(a_1,a_2)$ đều có một $x$ ánh xạ tới nó (nên $\psi$ toàn ánh) và $x$ đó duy nhất theo môđun $m_1 m_2$ (nên $\psi$ đơn ánh). Do đó $\psi$ là song ánh và vì thế là đẳng cấu vành.

Cuối cùng, trong vành tích $R_1\times R_2$, một phần tử $(u_1,u_2)$ có nghịch đảo nhân $(v_1,v_2)$ khi và chỉ khi $u_1 v_1=1$ trong $R_1$ và $u_2 v_2=1$ trong $R_2$ — tức khi và chỉ khi cả hai tọa độ đều khả nghịch. Vì đẳng cấu vành bảo toàn tính khả nghịch, các phần tử khả nghịch của $\mathbb{Z}/(m_1 m_2)\mathbb{Z}$ (có $\varphi(m_1 m_2)$ phần tử) tương ứng song ánh với các cặp phần tử khả nghịch trong $(\mathbb{Z}/m_1\mathbb{Z})\times(\mathbb{Z}/m_2\mathbb{Z})$ (có $\varphi(m_1)\,\varphi(m_2)$ cặp). Đếm hai vế cho $\varphi(m_1 m_2)=\varphi(m_1)\,\varphi(m_2)$. Kết hợp với $\varphi(p^r)=p^r-p^{r-1}$ cho lũy thừa nguyên tố (nơi các số không nguyên tố cùng nhau chỉ là $p^{r-1}$ bội của $p$), điều này lập tức suy ra công thức tích tổng quát cho $\varphi(n)$ đã dùng ở chủ đề trước. $\blacksquare$