Giải thích định lý số dư Trung Hoa

Một số chia 3 dư 2, chia 5 dư 3 và chia 7 dư 2. Đó là số nào? Thử lần lượt từng số thì sau một lúc bạn sẽ gặp 23, nhưng câu hỏi này ẩn chứa một định lý: miễn là các số chia không có ước chung, luôn có đúng một đáp án nhỏ hơn tích của chúng, và có thể tìm ra mà không cần thử gì cả. Định lý này đã khoảng 1.500 năm tuổi và vẫn đang làm việc trong lịch, trong phép tính của máy tính và trong mật mã bảo vệ web.

Ba hàng dấu cho các số chia 3 dư 2, chia 5 dư 3 và chia 7 dư 2, thẳng hàng trong một cột tại 23
Ba hàng dấu cho các số chia 3 dư 2, chia 5 dư 3 và chia 7 dư 2, thẳng hàng trong một cột tại 23

Một bài toán trong Tôn Tử toán kinh

Tôn Tử toán kinh, một sách số học Trung Hoa thế kỷ 3 đến 5, hỏi về một số vật mà đếm từng ba thì dư 2, đếm từng năm thì dư 3 và đếm từng bảy thì dư 2. Đáp án của sách là 23, và phương pháp của nó vẫn được dạy đến nay: lấy 70 cho mỗi vật dư khi đếm từng ba, 21 cho mỗi vật dư khi đếm từng năm và 15 cho mỗi vật dư khi đếm từng bảy, cộng lại rồi trừ 105 nhiều lần nhất có thể. 2 × 70 + 3 × 21 + 2 × 15 = 233, và 233 − 2 × 105 = 23. Một bài thơ thời Minh đã giữ các số 70, 21, 15 và 105 trong trí nhớ suốt nhiều thế kỷ. Tần Cửu Thiều đưa ra phương pháp tổng quát năm 1247, cùng bài toán ấy xuất hiện trong Liber Abaci của Fibonacci năm 1202, và Carl Friedrich Gauss phát biểu định lý ở dạng hiện đại trong Disquisitiones Arithmeticae năm 1801.

Một trang bản in đời Thanh của Tôn Tử Toán Kinh, sách số học Trung Hoa thế kỷ 3–5, hỏi một số khi đếm theo ba, năm và bảy thì dư lần lượt 2, 3 và 2.
Một trang bản in đời Thanh của Tôn Tử Toán Kinh, sách số học Trung Hoa thế kỷ 3–5, hỏi một số khi đếm theo ba, năm và bảy thì dư lần lượt 2, 3 và 2.
Carl Friedrich Gauss, trong chân dung năm 1840 của Christian Albrecht Jensen. Ông đưa ký hiệu đồng dư a ≡ b (mod n) vào Disquisitiones Arithmeticae năm 1801.
Carl Friedrich Gauss, trong chân dung năm 1840 của Christian Albrecht Jensen. Ông đưa ký hiệu đồng dư a ≡ b (mod n) vào Disquisitiones Arithmeticae năm 1801.

Định lý nói gì

Lấy các môđun n₁, n₂, …, nₖ sao cho không có hai môđun nào có ước chung, và các số dư a₁, a₂, …, aₖ tùy ý. Khi đó có đúng một số nguyên x từ 0 đến N − 1, với N = n₁ × n₂ × … × nₖ, chia nᵢ dư aᵢ với mọi i. Mọi nghiệm khác chênh lệch với nó một bội của N. Theo ký hiệu số học đồng dư: hệ x ≡ aᵢ (mod nᵢ) có nghiệm, và nghiệm đó duy nhất theo mod N. Nói cách khác, một số từ 0 đến N − 1 và danh sách số dư của nó mang đúng cùng một thông tin: 3 × 5 × 7 = 105 số và 3 × 5 × 7 = 105 danh sách số dư có thể có, mỗi danh sách được dùng đúng một lần.

Dựng nghiệm

Các số 70, 21 và 15 không có gì thần bí. Mỗi số chia cho môđun của chính nó dư 1 và chia cho các môđun khác dư 0: 70 = 2 × 35 là bội của 5 và 7, và chia 3 dư 1. Tổng quát, ta lấy Nᵢ = N / nᵢ, là bội của mọi môđun trừ nᵢ, rồi nhân với yᵢ, nghịch đảo của Nᵢ mod nᵢ. Nghịch đảo tồn tại vì Nᵢ và nᵢ không có ước chung, và thuật toán Euclid mở rộng tìm ra nó: thuật toán thực hiện các phép chia Euclid để tìm ước chung lớn nhất rồi tính ngược về đẳng thức Bézout 1 = s × nᵢ + t × Nᵢ, nên t là nghịch đảo. Khi đó x = a₁N₁y₁ + a₂N₂y₂ + …, rút gọn theo mod N, khớp với mọi đồng dư, vì mỗi số hạng khớp với đồng dư của riêng nó và biến mất trong mọi đồng dư khác.

Từng đồng dư một

Có một cách thứ hai không cần tích của mọi môđun. Mọi nghiệm của x ≡ 2 (mod 3) có dạng x = 2 + 3t. Thế vào đồng dư tiếp theo: 2 + 3t ≡ 3 (mod 5), tức 3t ≡ 1 (mod 5), và nhân với 2, nghịch đảo của 3 mod 5, ta được t ≡ 2 (mod 5). Khi đó x = 2 + 3 × 2 = 8, và hai đồng dư đầu cùng nói rằng x ≡ 8 (mod 15). Lặp lại với đồng dư thứ ba: 8 + 15t ≡ 2 (mod 7) cho t ≡ 1, nên x ≡ 23 (mod 105). Phép thế này giữ cho các số nhỏ hơn, là cách máy tính thường giải những hệ như vậy, và vẫn dùng được khi các môđun có ước chung.

Các môđun có ước chung

Nếu hai môđun có ước chung, các đồng dư của chúng chồng lên nhau: x ≡ 1 (mod 4) đã nói rằng x lẻ, còn x ≡ 4 (mod 6) nói rằng x chẵn, nên không có x nào thỏa mãn cả hai. Tổng quát, x ≡ a (mod m) và x ≡ b (mod n) có thể cùng đúng khi và chỉ khi a và b cho cùng số dư khi chia cho g = gcd(m, n), tức là khi g chia hết a − b. Khi đó nghiệm là duy nhất theo mod lcm(m, n) = m × n / g, chứ không phải mod m × n. Câu đố cổ về giỏ trứng, lấy ra mỗi lần 2, 3, 4, 5 hoặc 6 quả thì dư 1 còn mỗi lần 7 quả thì không dư, có đáp án 301, lặp lại sau mỗi 420 = lcm(2, 3, 4, 5, 6, 7). Một hệ có nghiệm khi và chỉ khi mọi cặp đồng dư của nó tương thích, nên một hệ vô nghiệm luôn chứa một cặp mâu thuẫn.

Lịch, máy tính và RSA

Năm 1583, Joseph Scaliger kết hợp ba chu kỳ lịch, chu kỳ mặt trời 28 năm, chu kỳ mặt trăng 19 năm và indiction 15 năm, thành chu kỳ Julius dài 28 × 19 × 15 = 7.980 năm. Theo định lý, mỗi năm có một tổ hợp riêng của ba số thứ tự chu kỳ, và chu kỳ bắt đầu từ năm 4713 TCN, năm gần nhất mà cả ba đều bằng 1; các nhà thiên văn vẫn đếm ngày Julius từ đó. Máy tính dùng định lý này để tính với những số khổng lồ dưới dạng danh sách các số dư nhỏ, có thể cộng và nhân riêng rẽ, song song, rồi ghép lại ở cuối. Giải mã RSA cũng vậy: c^d mod n với n = p × q được tính như hai phép lũy thừa mod p và mod q rồi ghép bằng định lý, nhanh hơn khoảng bốn lần so với một phép lũy thừa mod n. Các lược đồ chia sẻ bí mật, như của Mignotte và của Asmuth và Bloom, giấu bí mật trong các số dư sao cho chỉ khi gom đủ số dư mới khôi phục được nó.

Ron Rivest, Adi Shamir và Len Adleman (từ trái sang phải)
Ron Rivest, Adi Shamir và Len Adleman (từ trái sang phải)

Tự thử

Mở máy tính để nhập bất kỳ hệ đồng dư nào, tới 20 đồng dư và số tối đa 200 chữ số, hoặc chọn một trong các ví dụ có lời giải: bài toán Tôn Tử, giỏ trứng, chu kỳ Julius, lịch chạy của hai xe buýt, giải mã RSA và một hệ vô nghiệm. Lời giải được viết bằng chính các số của bạn, theo cách dựng hoặc phép thế, với thuật toán Euclid mở rộng cho mọi nghịch đảo. Hình vẽ đánh dấu các số thỏa mãn từng đồng dư để bạn thấy cột duy nhất nơi tất cả gặp nhau, hoặc xếp số dư của hai đồng dư vào một bảng mà mỗi số có ô riêng.

Câu hỏi thường gặp

Nghiệm của hệ đồng dư có duy nhất không?

Chỉ duy nhất nếu không tính đến bội của môđun. Nếu x = 23 là nghiệm của bài toán Tôn Tử thì 23 + 105 = 128, 233 và −82 cũng là nghiệm, vì cộng thêm 105 không làm thay đổi số dư nào. Định lý nói rằng có đúng một nghiệm từ 0 đến 104; với các môđun có ước chung, có đúng một nghiệm nhỏ hơn bội chung nhỏ nhất của chúng.

Vì sao các môđun phải nguyên tố cùng nhau?

Với cách dựng, vì Nᵢ phải có nghịch đảo mod nᵢ, mà nghịch đảo chỉ tồn tại khi chúng không có ước chung. Với chính định lý, vì ước chung làm một số đồng dư chồng lên nhau: khi đó hệ hoặc vô nghiệm, hoặc có ít nghiệm khác nhau hơn, và nghiệm lặp lại sau mỗi bội chung nhỏ nhất chứ không phải sau mỗi tích.

Làm sao tìm nghịch đảo modulo bằng tay?

Dùng thuật toán Euclid mở rộng. Với nghịch đảo của 15 mod 7: 15 = 2 × 7 + 1, nên 1 = 15 − 2 × 7, và 15 × 1 ≡ 1 (mod 7): nghịch đảo là 1. Với 35 mod 3: 35 = 11 × 3 + 2 và 3 = 1 × 2 + 1, nên 1 = 3 − 2 = 3 − (35 − 11 × 3) = 12 × 3 − 35, và nghịch đảo của 35 mod 3 là −1 ≡ 2. Với môđun nhỏ, bạn cũng có thể thử lần lượt 1, 2, 3, … cho đến khi tích chia dư 1.

Định lý này liên quan gì đến đồng hồ?

Một số dư mod n là một vị trí trên đồng hồ n giờ. Hai đồng hồ 3 giờ và 5 giờ, cùng khởi động và mỗi lần nhích một giờ, sẽ hiển thị mỗi cặp trong 15 cặp vị trí đúng một lần trước khi quay về điểm đầu, vì 3 và 5 không có ước chung. Đồng hồ 4 giờ và 6 giờ quay về sau 12 bước và chỉ hiển thị 12 trong 24 cặp: một vị trí lẻ và một vị trí chẵn không bao giờ xuất hiện cùng nhau.

Sẵn sàng thử chưa?

Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.

Mở máy tính định lý số dư Trung Hoa