Hàn Tín Điểm Quân và Định Lý Số Dư Trung Quốc

1. Giai thoại Hàn Tín điểm quân

Hàn Tín là danh tướng thời Tây Hán (thế kỷ II trước Công nguyên). Tương truyền, trong một buổi duyệt binh, ông không trực tiếp đếm quân mà yêu cầu binh lính xếp đội hình theo nhiều cách khác nhau:

• Xếp thành 3 hàng thì thừa 2 người
• Xếp thành 5 hàng thì thừa 3 người
• Xếp thành 7 hàng thì thừa 2 người

Khi viên tướng báo cáo có 2345 quân, Hàn Tín lập tức khẳng định:

“Không đúng. Thực tế chỉ có 2333 người.”

Kiểm tra lại cho thấy kết quả hoàn toàn chính xác. Bí quyết của Hàn Tín nằm ở quy luật số dư.

2. Bài toán trong Tôn Tử Toán Kinh

Giai thoại trên được hệ thống hóa trong sách Tôn Tử Toán Kinh (thế kỷ III) dưới dạng bài toán:

Tìm số nguyên \(x\) sao cho:

$$ \begin{aligned} x &\equiv 2 \pmod{3} \\ x &\equiv 3 \pmod{5} \\ x &\equiv 2 \pmod{7} \end{aligned} $$

Đây chính là dạng nguyên thủy của Định lý số dư Trung Quốc (Chinese Remainder Theorem – CRT).

3. Cách giải cổ điển

Xét các tích:

• \(70 = 5 \times 7\) → chia cho 3 dư 1
• \(21 = 3 \times 7\) → chia cho 5 dư 1
• \(15 = 3 \times 5\) → chia cho 7 dư 1

Nhân với các số dư tương ứng:

$$70 \cdot 2 + 21 \cdot 3 + 15 \cdot 2 = 233$$

Vì \(3 \cdot 5 \cdot 7 = 105\), nghiệm tổng quát là:

$$x = 233 + 105k,\quad k \in \mathbb{Z}$$

Do số quân không vượt quá 2345, ta chọn \(k = 20\) và thu được:

$$x = 2333$$

4. Bài ca dân gian – thuật toán bằng lời

Ba người cùng đi, bảy mươi hiếm có
Năm cây hoa mai, hai mươi mốt cành
Bảy con đoàn tụ, mười lăm trăng rằm
Muốn cho rõ ràng, trừ trăm linh năm

Bài ca mô tả chính xác quy trình: nhân số dư với tích các mô-đun còn lại, cộng lại, rồi trừ bội chung 105 cho đến khi được số nhỏ nhất dương.

5. Phương pháp "ngốc" của Hoa La Canh

Nhà toán học Hoa La Canh (1910–1985) gọi một cách tiếp cận khác là phương pháp ngốc, nhưng thực chất rất hiệu quả:

• Bắt đầu từ số dư nhỏ nhất
• Cộng dần theo mô-đun
• Dừng lại khi thỏa mãn điều kiện tiếp theo

2 → 5 → 8 → 23  

Đây là tư duy gia tăng có kiểm soát, rất gần với cách máy tính tìm nghiệm ngày nay.

6. Dạng tổng quát – Định lý số dư Trung Quốc

Cho các số \(a_1, a_2, \dots, a_n\) nguyên tố cùng nhau từng đôi một. Hệ:

$$\begin{aligned} N &\equiv r_1 \pmod{a_1} \\ N &\equiv r_2 \pmod{a_2} \\ &\vdots \end{aligned}$$

có nghiệm duy nhất theo modulo \(A = a_1 a_2 \cdots a_n\).

Điều kiện nguyên tố cùng nhau là bắt buộc. Nếu không, nghiệm có thể không tồn tại hoặc không duy nhất.

Đây là nơi GCD và thuật toán Euclid mở rộng đóng vai trò quyết định.

Nguyên lý cốt lõi:

Một bài toán lớn trong số học có thể được chia thành nhiều bài toán nhỏ độc lập, sau đó ghép nghiệm lại mà không mất thông tin.

7. Ý nghĩa hiện đại

• Lý thuyết số
• Mật mã học (RSA)
• Tính toán song song
• Hệ thống phân tán

Mặc dù không áp dụng trực tiếp cho hồi quy tuyến tính trong Machine Learning, tư duy chia – giải – ghép của CRT vẫn xuất hiện rộng rãi trong khoa học dữ liệu hiện đại.

8. Kết luận

“Hàn Tín điểm quân” không phải là câu chuyện huyền bí, mà là minh chứng cho trí tuệ toán học sâu sắc từ hơn 2000 năm trước.

Từ một bài toán đếm quân đơn giản, con người đã xây dựng nên một trong những định lý quan trọng nhất của toán học rời rạc.