5. Định lý số dư Trung Hoa¶
Định lý số dư Trung Hoa (Chinese Remainder Theorem - CRT) là một trong những định lý quan trọng nhất của số học nói riêng và toán học nói chung.
5.1. Chứng minh định lý số dư Trung Hoa¶
Giả sử ta có hệ phương trình đồng dư
Trong đó \(\gcd(m_i, m_j) = 1\) với mọi \(i \neq j\), \(1 \leqslant i, j \leqslant k\).
Khi đó định lý số dư Trung Hoa phát biểu rằng hệ phương trình đồng như này có nghiệm duy nhất trong modulo \(M = m_1 m_2 \ldots m_k\).
Chứng minh
Chúng ta cần chứng minh sự tồn tại và tính duy nhất của nghiệm.
Để chứng minh sự tồn tại, ta xây dựng cách tính nghiệm bằng quy nạp.
Bước cơ sở. Với \(k = 2\), ta có \(x \equiv x_1 \pmod{m_1}\) và \(x \equiv x_2 \pmod{m_2}\).
Do \(\gcd(m_1, m_2) = 1\) nên tồn tại hai số nguyên \(n_1\), \(n_2\) sao cho \(m_1 n_1 + m_2 n_2 = 1\) (bổ đề Bézout).
Quan sát một chút, nếu ta modulo hai vế \(m_1 n_1 + m_2 n_2 = 1\) cho \(m_1\) thì sẽ có \(m_2 n_2 \equiv 1 \pmod{m_1}\). Như vậy
Tương tự, \(m_1 n_1 \equiv 1 \pmod{m_2}\) nên
Từ đó ta có công thức nghiệm là
Khi modulo cho \(m_1\) và \(m_2\) thì kết quả là hai phương trình đồng dư ban đầu.
Tiếp theo chúng ta sử dụng quy nạp để chứng minh với mọi \(k \geqslant 2\) thì nghiệm của hệ phương trình đồng dư là
Trong đó
\(M = m_1 \cdot m_2 \cdots m_k\);
\(M_i = M / m_i\);
\(N_i\) là nghịch đảo của \(M_i\) trong modulo \(m_i\).
Giả thiết quy nạp. Giả sử (5.1) đúng với \(k \geqslant 2\). Đặt \(M = m_1 \cdots m_k\) và
Với \(k+1\) ta có
Tương tự với hai modulo ở bước cơ sở, do \(\gcd(m_{k+1}, m_i) = 1\) với mọi \(1 \leqslant i \leqslant k\) nên
Khi đó tồn tại các số nguyên \(\alpha\) và \(\beta\) sao cho \(\alpha M + \beta m_{k+1} = 1\).
Nghiệm của hệ hai phương trình đồng dư khi này là
Đặt \(M' = M \cdot m_{k+1} = m_1 \cdots m_k \cdot m_{k+1}\). Ở đây \(M = M' / m_{k+1}\) chính là \(M'_{k+1}\) trong cách xây dựng nghiệm ở trên.
Từ đó \(\alpha\) chính là \(N'_{k+1}\).
Ta có
Để ý rằng
nên suy ra
Tiếp theo, do \(\beta m_{k+1} \equiv 1 \pmod{M}\) và \(M = m_1 \cdots m_k\) nên \(\beta m_{k+1} \equiv 1 \pmod{m_i}\) với \(1 \leqslant i \leqslant k\).
Ở trên ta có \(N_i M_i \equiv 1 \pmod{m_i}\) nên suy ra \(\beta m_{k+1} \cdot N_i M_i \equiv 1 \pmod{m_i}\), tương đương với \((\beta N_i) \cdot (M_i m_{k+1}) \equiv 1 \pmod{m_i}\).
Ta đã chứng minh ở trước \(M_i m_{k+1} = M'/m_i = M'_i\) nên \(\beta N_i = N'_i\). Tới đây thì ta đã hoàn thành chứng minh do
Để chứng minh sự duy nhất của nghiệm, giả sử \(y\) là một nghiệm khác \(x\) của hệ phương trình đồng dư (modulu \(M\)). Khi đó \(y \equiv x_i \equiv x \pmod{m_i}\). Như vậy \(y = x + t_i m_i\), hay nói cách khác \(y\) khác \(x\) một bội của \(m_i\). Do đó trong modulo \(m_i\) chỉ có thể có trường hợp \(y \equiv x\) nên nghiệm tìm được ở modulo tổng là duy nhất.
Ví dụ 5.5
Tìm nghiệm của hệ phương trình đồng dư sau
Ta có \(\gcd(3, 7) = 1\) và \(3 \cdot 5 + 7 \cdot (-2) = 1\). Do đó nghiệm của hệ phương trình có dạng
Ta kiểm tra \(4 \equiv 1 \pmod 3\) và \(4 \equiv 4 \pmod 7\) thỏa mãn hệ phương trình đồng dư.
5.2. Bài tập sưu tầm¶
Câu 1 (đề kiểm tra, ITMO). Giải hệ đồng dư
Do \(\gcd(56, 77) = 7\) nên đầu tiên cần tách mỗi phương trình thành các module nguyên tố cùng nhau.
Sử dụng định lý số dư Trung Hoa cho hệ
giải ra nghiệm \(x \equiv 179 \pmod{616}\).
Câu 2 (đề kiểm tra, ITMO). Tìm hai chữ số cuối của số
Tìm hai chữ số cuối cũng có nghĩa là tính đồng dư trong modulo \(100\).
Thay vì tính trong modulo \(100\), chúng ta tính trong modulo \(4\) và \(25\) rồi dùng định lý số dư Trung Hoa để gom nghiệm lại.
Đặt \(A = 318^{17683732657328}\).
Vì \(318 \equiv 0 \pmod 2\) nên \(318^2 \equiv 0 \pmod{2^2}\). Nói cách khác \(A \equiv 0 \pmod 4\).
Vì \(\gcd(318, 25) = 1\) nên \(318^{\varphi(25)} \equiv 1 \pmod{25}\). Do \(\varphi(25) = 20\) nên suy ra
Như vậy chỉ cần tính \(318^{8} \pmod{25}\) nữa. Vì \(318 \equiv 18 \pmod{25}\), ta tính
Như vậy \(318^{8} \equiv 1 \pmod{25}\). Ta có hệ đồng dư
Như vậy \(A \equiv 76 \pmod{100}\). Vậy hai chữ số cuối là \(76\).
Câu 3 (đề kiểm tra, ITMO). Tìm tất cả nghiệm của phương trình
Vì \(5929 = 7^2 \cdot 11^2\) nên ta giải trên hai modulo \(7^2\) và \(11^2\).
Trên modulo \(7^2\), vì chỉ có \(\pm 1\) thỏa \(x^2 \pmod 7\) nên cũng chỉ có \(\pm 1\) thỏa \(x^2 \equiv 1 \pmod{7^2}\).
Tương tự, trên modulo \(11^2\), vì chỉ có \(\pm 1\) thỏa \(x^2 \pmod{11}\) nên cũng chỉ có \(\pm 1\) thỏa \(x^2 \equiv 1 \pmod{11^2}\).
Ta tính \((7^2)^{-1} \equiv 42 \pmod{11^2}\) và \((11^2)^{-1} \equiv 32 \pmod{7^2}\).
Khi đó nghiệm của phương trình
cũng là nghiệm của hệ
Như vậy có \(4\) nghiệm là