Thi đấu

Định Lý Thặng Dư Trung Hoa (CRT) và Hệ Phương Trình Đồng Dư

Định lý thặng dư Trung Hoa (CRT) tìm nghiệm nguyên duy nhất theo modulo tích cho một hệ phương trình đồng dư với các modulo đôi một nguyên tố cùng nhau.

Định Lý Thặng Dư Trung Hoa (CRT) và Hệ Phương Trình Đồng Dư

Trong cuốn sách toán cổ "Tôn Tử toán kinh" ra đời từ thế kỷ thứ 3, một bài toán đố nổi tiếng được đặt ra: "Có một số vật không rõ số lượng. Đếm theo từng nhóm 3 thì dư 2, đếm theo nhóm 5 thì dư 3, và đếm theo nhóm 7 thì dư 2. Hỏi có bao nhiêu vật?". Bài toán đố cổ xưa này chính là khởi nguồn của một trong những định lý nền tảng rực rỡ nhất của số học thế giới: Định lý Thặng dư Trung Hoa (Chinese Remainder Theorem - CRT).

Trong thời đại lập trình thi đấu và mật mã học hiện đại (đặc biệt là hệ mật RSA), định lý CRT không chỉ là công cụ giải các câu đố số học mà còn là giải pháp kỹ thuật tối ưu giúp chia nhỏ các phép tính trên số nguyên khổng lồ thành các phép tính độc lập trên các modulo nhỏ, sau đó ghép nối lại một cách hoàn hảo.

Bài viết này sẽ hướng dẫn bạn toàn bộ công thức toán học tường minh, thuật toán xây dựng nghiệm duy nhất bằng thuật toán Euclid mở rộng, và kỹ thuật giải bài toán tổng quát khi các modulo không nguyên tố cùng nhau.

1. Phát biểu Định lý Thặng Dư Trung Hoa

Xét hệ \(k\) phương trình đồng dư bậc nhất với ẩn số nguyên \(x\):

\[\begin{cases} x \equiv r_1 \pmod{m_1} \\ x \equiv r_2 \pmod{m_2} \\ \dots \\ x \equiv r_k \pmod{m_k} \end{cases}\]

Định lý CRT phát biểu rằng: Nếu các số nguyên dương \(m_1, m_2, \dots, m_k\) nguyên tố cùng nhau từng đôi một (tức \(\gcd(m_i, m_j) = 1\) với mọi \(i \ne j\)), thì hệ phương trình luôn có một nghiệm nguyên duy nhất theo modulo \(M = m_1 \cdot m_2 \dots m_k\), nghĩa là mọi nghiệm của hệ đều có dạng:

\[x \equiv x_0 \pmod M\]

với \(x_0 \in [0, M - 1]\).

Định Lý Thặng Dư Trung Hoa (CRT) & Hệ Phương Trình Đồng Dư Giải hệ x ≡ r_i (mod m_i) với các m_i nguyên tố cùng nhau từng đôi một -> Ví dụ x ≡ 2(mod 3), 3(mod 5), 2(mod 7) => x = 23 Thuật toán xây dựng nghiệm duy nhất 1. M = m1 * m2 * ... * mk 2. Mi = M / mi với mỗi phương trình i 3. yi = modInverse(Mi, mi) Công thức nghiệm x mod M: x = ∑ (r_i * Mi * yi) mod M Nghiệm duy nhất trong đoạn [0, M - 1] Chạy tay: m = {3, 5, 7}, r = {2, 3, 2} Tích M = 3 * 5 * 7 = 105 • M1 = 35; y1 = 35^-1 mod 3 = 2^-1 mod 3 = 2 • M2 = 21; y2 = 21^-1 mod 5 = 1^-1 mod 5 = 1 • M3 = 15; y3 = 15^-1 mod 7 = 1^-1 mod 7 = 1 x = 2*35*2 + 3*21*1 + 2*15*1 x = 140 + 63 + 30 = 233 ≡ 23 (mod 105) => Nghiệm nhỏ nhất x = 23!
Định Lý Thặng Dư Trung Hoa (CRT) Giải hệ đồng dư trong O(K log M) Các bước thực hiện: M = ∏ m_i; M_i = M / m_i y_i = M_i^-1 mod m_i x = ∑ (r_i * M_i * y_i) % M Ví dụ hệ 3 phương trình: x ≡ 2(mod 3), x ≡ 3(mod 5), x ≡ 2(mod 7) M = 105; x = 233 ≡ 23 (mod 105) 23%3=2, 23%5=3, 23%7=2 => Thỏa mãn mọi điều kiện!
Quy trình xây dựng nghiệm x = 23 cho hệ 3 phương trình đồng dư modulo 3, 5, 7.

2. Thuật toán xây dựng nghiệm trực tiếp

Thuật toán giải bài toán CRT dựa trên phương pháp kiến tạo tường minh qua 4 bước:

Bước 1: Tính tích của tất cả các modulo

\[M = \prod_{i=1}^k m_i = m_1 \cdot m_2 \dots m_k\]

Bước 2: Tính các đại lượng thành phần M_i

Với mỗi phương trình thứ \(i\), ta tính \(M_i\) bằng cách loại bỏ chính \(m_i\) khỏi tích chung: \[M_i = \frac{M}{m_i} = \prod_{j \ne i} m_j\] Nhận xét quan trọng: Do \(M_i\) chứa thừa số \(m_j\) với mọi \(j \ne i\), nên \(M_i \equiv 0 \pmod{m_j}\) với mọi \(j \ne i\).

Bước 3: Tìm phần tử nghịch đảo y_i

Vì các \(m_i\) nguyên tố cùng nhau từng đôi một, nên \(\gcd(M_i, m_i) = 1\). Ta luôn tìm được nghịch đảo modulo \(y_i\) thỏa mãn: \[M_i \cdot y_i \equiv 1 \pmod{m_i}\] Giá trị \(y_i\) được tính nhanh chóng bằng thuật toán Euclid mở rộng: extgcd(M_i, m_i, y_i, temp).

Bước 4: Ghép nghiệm tổng quát

Xét số nguyên \(x\) được xây dựng theo tổ hợp tuyến tính: \[x = \sum_{i=1}^k r_i \cdot M_i \cdot y_i \pmod M\]

Tại sao nghiệm này luôn đúng? Lấy số \(x\) chia lấy dư cho một modulo \(m_j\) bất kỳ:

  • Với mọi số hạng \(i \ne j\): đại lượng \(M_i\) chia hết cho \(m_j\), nên \(r_i \cdot M_i \cdot y_i \equiv 0 \pmod{m_j}\).
  • Với số hạng \(i = j\): ta có \(M_j \cdot y_j \equiv 1 \pmod{m_j}\), do đó số hạng này đồng dư với \(r_j \cdot 1 = r_j \pmod{m_j}\). Kết quả là \(x \equiv r_j \pmod{m_j}\) được thỏa mãn đồng thời cho mọi \(j \in \{1, \dots, k\}\)!

3. Chạy tay ví dụ cổ điển của Tôn Tử

Xét hệ phương trình: \[\begin{cases} x \equiv 2 \pmod 3 \\ x \equiv 3 \pmod 5 \\ x \equiv 2 \pmod 7 \end{cases}\]

  1. Tính tích \(M = 3 \times 5 \times 7 = 105\).
  2. Tính các giá trị \(M_i\):
    • \(M_1 = 105 / 3 = 35\)
    • \(M_2 = 105 / 5 = 21\)
    • \(M_3 = 105 / 7 = 15\)
  3. Tìm nghịch đảo modulo \(y_i\):
    • \(35 \cdot y_1 \equiv 1 \pmod 3 \implies 2 \cdot y_1 \equiv 1 \pmod 3 \implies y_1 = 2\).
    • \(21 \cdot y_2 \equiv 1 \pmod 5 \implies 1 \cdot y_2 \equiv 1 \pmod 5 \implies y_2 = 1\).
    • \(15 \cdot y_3 \equiv 1 \pmod 7 \implies 1 \cdot y_3 \equiv 1 \pmod 7 \implies y_3 = 1\).
  4. Tính tổng: \[x = (2 \times 35 \times 2) + (3 \times 21 \times 1) + (2 \times 15 \times 1) = 140 + 63 + 30 = 233\] Rút gọn theo modulo 105: \[x_0 = 233 \pmod{105} = 23\] Kiểm tra lại: \(23 = 7 \times 3 + 2\), \(23 = 4 \times 5 + 3\), \(23 = 3 \times 7 + 2\). Khớp hoàn toàn với lời giải cổ xưa!

4. Cài đặt thuật toán CRT bằng C++ và Python

Code dưới đây giả sử \(0 \le r_i < m_i\) và tích \(M\) vừa kiểu long long. Ngoài hệ của Tôn Tử, hàm main() còn khôi phục số \(x = 987654321987654321\) từ hai số dư của nó theo hai modulo \(10^9 + 7\) và \(998244353\) (\(M \approx 10^{18}\)). Ở ví dụ này tích trung gian \(r_i \cdot M_i \cdot y_i\) vượt \(2^{63}\): nếu nhân bằng long long thì khi thử với g++, chương trình in ra \(485006536873379668\) thay vì \(x\); vì vậy bản C++ nhân bằng __int128.

Cài đặt C++17

#include <iostream>
#include <vector>

using namespace std;

// Tim nghich dao modulo bang thuat toan Euclid dang vong lap
long long modular_inverse(long long val, long long mod) {
    long long m0 = mod, t, q;
    long long x0 = 0, x1 = 1;
    if (mod == 1) return 0;
    while (val > 1) {
        q = val / mod;
        t = mod; mod = val % mod; val = t;
        t = x0; x0 = x1 - q * x0; x1 = t;
    }
    if (x1 < 0) x1 += m0;
    return x1;
}

// Giai he dong du CRT trong O(K log M), voi 0 <= r[i] < m[i] va tich M vua long long
long long chinese_remainder_theorem(const vector<long long>& r, const vector<long long>& m) {
    int k = r.size();
    long long M = 1;
    for (int i = 0; i < k; ++i) M *= m[i];
    
    long long ans = 0;
    for (int i = 0; i < k; ++i) {
        long long Mi = M / m[i];
        long long yi = modular_inverse(Mi, m[i]);
        // Tich r[i] * Mi * yi co the vuot 2^63 ngay ca khi M vua long long: nhan bang __int128
        long long term = (long long)((__int128)r[i] * Mi % M * yi % M);
        ans = (long long)(((__int128)ans + term) % M);
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // He: x == 2 (mod 3), x == 3 (mod 5), x == 2 (mod 7) -> Ket qua x = 23
    vector<long long> r = {2, 3, 2};
    vector<long long> m = {3, 5, 7};
    cout << chinese_remainder_theorem(r, m) << '\n';
    
    // Hai modulo NTT 10^9 + 7 va 998244353: M ~ 10^18 van vua long long
    // Khoi phuc x = 987654321987654321 tu hai so du cua no
    cout << chinese_remainder_theorem({74074116, 930818242}, {1000000007, 998244353}) << '\n';
    return 0;
}

Cài đặt Python 3

import sys

def modular_inverse(val: int, mod: int) -> int:
    """Nghich dao modulo su dung pow hoac thuat toan Euclid mo rong."""
    return pow(val, -1, mod)

def chinese_remainder_theorem(r: list[int], m: list[int]) -> int:
    k = len(r)
    M = 1
    for mod in m:
        M *= mod
    ans = 0
    for i in range(k):
        Mi = M // m[i]
        yi = modular_inverse(Mi, m[i])
        term = (r[i] * Mi * yi) % M
        ans = (ans + term) % M
    return ans

def main():
    r = [2, 3, 2]
    m = [3, 5, 7]
    print(chinese_remainder_theorem(r, m))
    # So nguyen cua Python khong gioi han do dai nen khong lo tran so
    print(chinese_remainder_theorem([74074116, 930818242], [1000000007, 998244353]))

if __name__ == '__main__':
    main()

5. Mở rộng: Khi các Modulo không nguyên tố cùng nhau

Trong các đề thi nâng cao, giả thiết \(\gcd(m_i, m_j) = 1\) có thể bị phá vỡ. Khi đó, ta giải quyết bài toán bằng cách gộp từng cặp phương trình: Xét hai phương trình: \[x \equiv r_1 \pmod{m_1} \implies x = m_1 \cdot p + r_1\] \[x \equiv r_2 \pmod{m_2} \implies m_1 \cdot p + r_1 \equiv r_2 \pmod{m_2}\] Chuyển vế: \[m_1 \cdot p \equiv (r_2 - r_1) \pmod{m_2}\] Phương trình này là dạng phương trình Diophantine tuyến tính:

  • Nếu \((r_2 - r_1)\) không chia hết cho \(g = \gcd(m_1, m_2)\), hệ vô nghiệm.
  • Ngược lại, ta tìm được nghiệm \(p\), từ đó suy ra nghiệm \(x\) mới theo modulo \(\text{lcm}(m_1, m_2)\). Lặp lại quá trình này \(k - 1\) lần để gộp cả hệ thành một phương trình duy nhất!

Bảng so sánh các phương pháp giải hệ phương trình đồng dư

Tùy vào tính chất của các modulo và độ lớn của dữ liệu, ta có các hướng tiếp cận khác nhau:

Phương pháp Độ phức tạp Phạm vi áp dụng Ưu điểm Nhược điểm
Duyệt bước nhảy (Stepping) \(O(M)\) Số phương trình ít, tích \(M \le 10^7\) Dễ cài đặt, không cần nghịch đảo modulo Chạy rất chậm khi modulo lớn
CRT truyền thống \(O(K \log M)\) Các \(m_i\) nguyên tố cùng nhau đôi một Nghiệm tường minh, tính toán độc lập Dễ tràn số 64-bit khi tích \(M\) lớn
Gộp từng cặp bằng Euclid mở rộng \(O(K \log M)\) Modulo bất kỳ (không cần nguyên tố cùng nhau) Xử lý được mọi hệ phương trình tổng quát Cài đặt phức tạp hơn
Thuật toán Garner \(O(K^2)\) Modulo nguyên tố cùng nhau, tích \(M\) cực lớn Không bao giờ bị tràn số lớn Cần xử lý biểu diễn cơ số hỗn hợp

Ví dụ chi tiết gộp hai phương trình khi modulo không nguyên tố cùng nhau

Xét hệ hai phương trình với các modulo không nguyên tố cùng nhau: \[\begin{cases} x \equiv 3 \pmod 4 \\ x \equiv 5 \pmod 6 \end{cases}\]

Ta thấy \(\gcd(4, 6) = 2 \ne 1\), do đó không thể áp dụng trực tiếp công thức CRT cổ điển. Biểu diễn phương trình thứ nhất: \(x = 4p + 3\). Thay vào phương trình thứ hai: \[4p + 3 \equiv 5 \pmod 6 \implies 4p \equiv 2 \pmod 6\]

Phương trình này có dạng \(a \cdot p \equiv b \pmod m\) với \(a = 4, b = 2, m = 6\). Vì \(\gcd(4, 6) = 2\) và \(b = 2\) chia hết cho 2, nên phương trình chắc chắn có nghiệm! Chia cả hai vế và modulo cho 2: \[2p \equiv 1 \pmod 3\] Nghịch đảo modulo của 2 theo modulo 3 là 2 (vì \(2 \times 2 = 4 \equiv 1 \pmod 3\)). Nhân 2 vào cả hai vế: \[p \equiv 2 \times 1 \equiv 2 \pmod 3 \implies p = 3q + 2\]

Thế ngược lại \(p\) vào biểu thức của \(x\): \[x = 4(3q + 2) + 3 = 12q + 8 + 3 = 12q + 11\] Như vậy, hệ hai phương trình ban đầu được gộp thành duy nhất một phương trình đồng dư: \[x \equiv 11 \pmod{12}\] với modulo mới chính là \(\text{lcm}(4, 6) = 12\). Nghiệm nguyên dương nhỏ nhất là \(x = 11\). Kiểm tra lại: \(11 = 2 \times 4 + 3\) (dư 3) và \(11 = 1 \times 6 + 5\) (dư 5). Hoàn toàn chính xác!

Bốn lưu ý quan trọng khi lập trình CRT trong phòng thi

  1. Nguy cơ tràn số khi nhân tích các modulo: Nếu một hệ gồm 3 phương trình với các modulo xấp xỉ \(10^9\), tích \(M = m_1 \times m_2 \times m_3 \approx 10^{27}\), vượt xa giới hạn \(9.2 \times 10^{18}\) của kiểu long long. Ngay cả khi \(M\) còn vừa long long (hai modulo \(10^9 + 7\) và \(998244353\) cho \(M \approx 10^{18}\)), tích trung gian \(r_i \cdot M_i \cdot y_i\) đã có thể vượt \(2^{63}\), vì vậy code ở mục 4 nhân bằng __int128. Trong C++, bạn nên dùng kiểu __int128_t của trình biên dịch GCC để thực hiện các phép nhân tích lũy trung gian. Trong Python, số nguyên hỗ trợ độ dài vô hạn nên hoàn toàn miễn nhiễm với lỗi này.

  2. Kiểm tra tính vô nghiệm của hệ: Khi gộp hai phương trình có \(\gcd(m_1, m_2) = g\), nếu hiệu \((r_2 - r_1)\) không chia hết cho \(g\), hệ phương trình vô nghiệm. Cần lập tức thông báo không có nghiệm thay vì tiếp tục tính toán dẫn tới kết quả sai.

  3. Ứng dụng của CRT trong thuật toán biến đổi Fourier nhanh (NTT): Khi nhân hai đa thức lớn với đáp số vượt quá một modulo nguyên tố thông thường, ta chọn 3 modulo nguyên tố NTT thân thiện (ví dụ \(998244353, 1004535809, 469762049\)). Nhân đa thức độc lập trên từng modulo rồi dùng định lý CRT khôi phục hệ số thực.

  4. Kỹ thuật chuẩn hóa số dư âm: Khi tính toán đại lượng \(r_2 - r_1\), kết quả có thể mang dấu âm. Trước khi thực hiện phép chia lấy dư, luôn cộng thêm modulo: (r2 - r1 % m2 + m2) % m2.

Luyện ngay trên Big-O Coding

Hãy thực hành ngay các bài toán số học đồng dư nâng cao trên Big-O Coding:

Làm thế nào để tránh tràn số khi tích M vượt quá 10^18?

Nếu tích \(M\) vượt quá phạm vi kiểu long long, bạn có hai giải pháp: sử dụng kiểu dữ liệu __int128_t trong trình biên dịch GCC C++, hoặc sử dụng ngôn ngữ Python vốn tự động hỗ trợ số nguyên lớn không giới hạn độ dài. Trong C++, __int128_t có giá trị tối đa \(2^{127} - 1 \approx 1.7 \times 10^{38}\), đủ chứa tích của 4 số nguyên \(10^9\); nhưng khi ghép CRT với 4 modulo cỡ \(10^9\), tích trung gian \(r_i \cdot M_i \cdot y_i\) (cỡ \(10^{45}\)) vẫn tràn, khi đó nên dùng thuật toán Garner hoặc Python.

Ứng dụng của định lý CRT trong thuật toán chia đa thức và FFT là gì?

Khi thực hiện nhân hai đa thức hệ số lớn bằng thuật toán biến đổi Fourier nhanh NTT (Number Theoretic Transform), một modulo nguyên tố thường không đủ để chứa kết quả nhân. Người ta chọn 3 modulo nguyên tố đặc biệt khác nhau (thường là \(998244353, 1004535809, 469762049\)), tính tích đa thức độc lập trên từng modulo, rồi dùng định lý CRT ghép lại để khôi phục chính xác hệ số thực tế!

Nguồn tham khảo

Muốn học bài bản cùng giảng viên?

Lộ trình 4 cấp độ cho học sinh thi Tin học trẻ, Chuyên Tin, Olympic, ACM-ICPC: xếp lớp theo năng lực, mini contest, lớp Đội tuyển. Học online, phí theo tháng.

Xem Tài năng lập trình

Nguồn tham khảo

Chia sẻ: Facebook LinkedIn
Nhắn Zalo tư vấnZalo Gọi 0937 401 483