Định lý Số dư Trung Hoa là gì?
Định lý Số dư Trung Hoa (Chinese Remainder Theorem - CRT) là một kết quả kinh điển trong lý thuyết số. Định lý khẳng định rằng nếu bạn có một hệ đồng dư \(x \equiv a_1 \pmod{m_1}\), \(x \equiv a_2 \pmod{m_2}\), … trong đó các module nguyên tố cùng nhau từng đôi một (không có ước chung), thì tồn tại duy nhất một nghiệm x theo module \(M = m_1 \cdot m_2 \cdot \ldots\). Máy tính này sẽ tìm cho bạn nghiệm không âm nhỏ nhất đó.
Cách sử dụng máy tính
Hãy nhập mỗi số dư \(a_i\) kèm theo module \(m_i\) tương ứng. Bạn có thể giải hệ gồm hai hoặc ba đồng dư — nếu chỉ cần hai thì để trống ô module thứ ba. Công cụ sẽ kiểm tra xem các module có nguyên tố cùng nhau từng đôi hay không, sau đó trả về x cùng module tổng hợp M. Mọi giá trị dạng \(x + Mk\) (với k là số nguyên bất kỳ) cũng đều là nghiệm.
Giải thích công thức
Đặt \(M = \prod m_i\). Với mỗi đồng dư, ta định nghĩa \(M_i = M / m_i\) và \(y_i = M_i^{-1} \bmod m_i\) (nghịch đảo theo module, tính bằng thuật toán Euclid mở rộng). Khi đó nghiệm là tổng có trọng số $$x \equiv \sum_{i} a_i\,M_i\,y_i \pmod{M}$$ Vì \(M_i\) chia hết cho mọi module trừ \(m_i\), nên mỗi số hạng chỉ đóng góp đúng số dư cho riêng đồng dư của nó.
Ví dụ minh họa
Giải hệ \(x \equiv 2 \pmod 3\) và \(x \equiv 1 \pmod 4\). Ở đây \(M = 3 \cdot 4 = 12\). \(M_1 = 4\), mà \(4 \equiv 1 \pmod 3\) nên \(y_1 = 1\); \(M_2 = 3\), mà \(3 \equiv 3 \pmod 4\) nên \(y_2 = 3\) (vì \(3 \cdot 3 = 9 \equiv 1\)). Vậy $$x = 2 \cdot 4 \cdot 1 + 1 \cdot 3 \cdot 3 = 8 + 9 = 17 \equiv 5 \pmod{12}$$ 5 (mod 12). Kiểm tra lại: \(5 \bmod 3 = 2\) ✓ và \(5 \bmod 4 = 1\) ✓.
Câu hỏi thường gặp
Tại sao các module phải nguyên tố cùng nhau? Nếu hai module có ước chung, hệ có thể vô nghiệm hoặc có nhiều nghiệm theo module là bội chung nhỏ nhất (lcm) của chúng, khi đó công thức CRT chuẩn không còn áp dụng được.
"Nghiệm không âm nhỏ nhất" nghĩa là gì? Tất cả các nghiệm chỉ chênh nhau một bội của M; máy tính sẽ trả về nghiệm nằm trong khoảng từ \(0\) đến \(M-1\).
Tôi có thể dùng số dư âm không? Có. Trước khi giải, chúng sẽ được rút gọn theo từng module \(m_i\) về khoảng từ \(0\) đến \(m_i-1\).
