Máy tính định lý số dư Trung Hoa
Đếm một đống đồ vật từng ba thì dư 2, từng năm thì dư 3, từng bảy thì dư 2: có 23 vật, hoặc 128, hoặc 233, cứ 105 lại có một đáp án. Đó là bài toán trong Tôn Tử toán kinh đã đặt tên cho định lý số dư Trung Hoa. Nhập bất kỳ hệ đồng dư x ≡ a (mod n) nào, với bao nhiêu đồng dư và số lớn bao nhiêu tùy ý, rồi xem đáp án, lời giải bằng chính các số của bạn và một hình vẽ cho thấy vì sao nó đúng. Khi các đồng dư không thể cùng đúng, máy tính chỉ ra hai đồng dư mâu thuẫn và cho biết lý do. Nhập các đồng dư x ≡ a (mod n), mỗi dòng một đồng dư: a là số dư và n là môđun. Thêm dòng bằng Thêm đồng dư, hoặc nhấn Enter ở môđun cuối cùng, và xóa dòng bằng ×. Có thể dùng số nguyên tới 200 chữ số, và a có thể âm. Hoặc chọn một ví dụ có lời giải. Các ô hiển thị nghiệm nhỏ nhất và chu kỳ lặp của nó; bên dưới là vài nghiệm dương đầu tiên và phép thử cho từng đồng dư. Hình vẽ đánh dấu các số thỏa mãn từng đồng dư, và cột có dấu ở mọi hàng chính là nghiệm; bảng số dư hiển thị hai đồng dư cùng lúc. Lời giải được viết bằng chính các số của bạn, theo cách dựng trong sách giáo khoa hoặc theo phép thế.
Cách nó hoạt động
- Nhập các đồng dư x ≡ a (mod n), mỗi dòng một đồng dư, hoặc chọn một ví dụ có lời giải như bài toán Tôn Tử, giỏ trứng hay chu kỳ Julius.
- Đọc nghiệm nhỏ nhất, môđun mà nghiệm lặp lại theo, và vài nghiệm dương đầu tiên, mỗi nghiệm đều được thử với mọi đồng dư.
- Theo dõi lời giải từng bước, theo cách dựng hoặc phép thế, và chuyển hình vẽ giữa trục số và bảng số dư.
Cách dựng hoạt động thế nào
Khi không có hai môđun nào có ước chung, có thể dựng nghiệm trực tiếp. Nhân các môđun: với bài toán Tôn Tử, N = 3 × 5 × 7 = 105. Với mỗi đồng dư lấy Nᵢ = N / nᵢ, là bội của mọi môđun khác: 35, 21 và 15. Rồi tìm nghịch đảo yᵢ của Nᵢ mod nᵢ bằng thuật toán Euclid mở rộng: 35 chia 3 dư 2, và 2 × 2 = 4 ≡ 1 (mod 3), nên y₁ = 2; 21 và 15 đều dư 1, nên nghịch đảo của chúng là 1. Khi đó x = 2 × 35 × 2 + 3 × 21 × 1 + 2 × 15 × 1 = 233, và 233 mod 105 = 23. Mỗi số hạng khớp với đồng dư của riêng nó và là bội của các môđun còn lại, nên tổng khớp với tất cả.
Khi các môđun có ước chung
Một hệ có các môđun chung ước vẫn có thể có nghiệm. Hai đồng dư x ≡ a (mod m) và x ≡ b (mod n) có thể cùng đúng khi và chỉ khi a − b là bội của gcd(m, n), và khi đó nghiệm lặp lại sau mỗi lcm(m, n) chứ không phải mỗi m × n. Hai xe buýt chạy ở phút thứ 5 và 11, cứ 12 và 18 phút một chuyến, gặp nhau ở phút thứ 29 và sau đó cứ 36 phút một lần, vì 11 − 5 = 6 là bội của gcd(12, 18) = 6. Nhưng x ≡ 1 (mod 4) và x ≡ 4 (mod 6) không bao giờ cùng đúng: đồng dư thứ nhất làm x lẻ, đồng dư thứ hai làm x chẵn. Cả hệ có nghiệm khi và chỉ khi mọi cặp đồng dư của nó có nghiệm, và đó là cách máy tính tìm ra hai đồng dư mâu thuẫn.
Câu hỏi thường gặp
Định lý số dư Trung Hoa nói gì?
Nếu không có hai trong các môđun n₁, n₂, … có ước chung, thì với mọi số dư a₁, a₂, … có đúng một x từ 0 đến N − 1 sao cho x ≡ aᵢ (mod nᵢ) với mọi i, trong đó N là tích các môđun. Mọi nghiệm khác chênh lệch với nó một bội của N: với bài toán Tôn Tử, các nghiệm là 23, 128, 233, v.v., cứ 105 lại có một nghiệm.
Vì sao gọi là Trung Hoa?
Bài toán cổ nhất được biết đến thuộc loại này nằm trong Tôn Tử toán kinh, một sách số học Trung Hoa viết vào khoảng thế kỷ 3 đến 5: đếm từng ba, từng năm, từng bảy thì một số vật dư 2, 3 và 2. Tần Cửu Thiều đưa ra phương pháp tổng quát cho các bài toán như vậy năm 1247, và Carl Friedrich Gauss phát biểu định lý ở dạng hiện đại năm 1801.
Nếu các môđun không nguyên tố cùng nhau thì sao?
Khi đó có thể không có nghiệm, và nếu có thì nghiệm lặp lại sau mỗi bội chung nhỏ nhất của các môđun chứ không phải sau mỗi tích. Hai đồng dư tương thích khi số dư của chúng bằng nhau theo môđun gcd của hai môđun. Câu đố giỏ trứng dùng 2, 3, 4, 5, 6 và 7, có ước chung, nhưng vẫn có nghiệm: 301, lặp lại sau mỗi 420.
RSA dùng định lý số dư Trung Hoa như thế nào?
Giải mã một thông điệp RSA là tính c^d mod n, với n = p × q. Sẽ nhanh hơn nếu tính riêng c^d mod p và c^d mod q, với số mũ được rút gọn theo mod p − 1 và q − 1, rồi ghép hai kết quả bằng định lý. Với các số dài bằng một nửa, mỗi phép lũy thừa chỉ tốn khoảng một phần tám công sức, nên giải mã nhanh hơn khoảng bốn lần, và phần lớn phần mềm RSA làm theo cách này.
Các số có thể lớn đến mức nào?
Tới 20 đồng dư, mỗi số tối đa 200 chữ số. Máy tính dùng số nguyên chính xác ngay trong trình duyệt của bạn, nên đáp án luôn chính xác dù dài đến đâu, và không có gì được gửi đi.
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.
Tới trình chỉnh sửa