Mánh Khóe Quân Sự Cổ Đại: Bí Ẩn Đằng Sau Định Lý Số Dư Trung Quốc

Câu Chuyện Tướng Quân Giấu Quân Số

Hãy hình dung bạn là một vị tướng quân thời cổ đại. Việc giữ kín quân số trước kẻ thù là điều tối quan trọng, nhưng bạn vẫn cần biết chính xác lực lượng của mình. Vậy làm thế nào để vừa biết, vừa giữ bí mật?

Bài toán thách đố từ ngàn xưa

Giả sử vào một buổi sáng tập luyện, bạn yêu cầu binh lính xếp hàng theo các đội hình khác nhau:

• Khi xếp thành hàng $5$, còn lại $3$ người ở hàng cuối.
• Khi xếp thành hàng $8$, còn lại $7$ người ở hàng cuối.
• Khi xếp thành hàng $9$, còn lại $2$ người ở hàng cuối.

Tuyệt vời! Bạn không cần phải đếm từng người lính, nhưng với những thông tin này, bạn đã có đủ dữ liệu để xác định tổng số quân mà không cần phải công bố con số cụ thể ra ngoài, tránh bị kẻ thù nắm bắt.

Truyền thuyết kể rằng các vị tướng quân Trung Quốc cổ đại đã thực sự áp dụng kỹ thuật này, mặc dù tính xác thực vẫn còn là một ẩn số. Điều chúng ta biết chắc chắn là kỹ thuật toán học này, ngày nay được gọi là Định lý Số dư Trung Quốc (Chinese Remainder Theorem), đã được nhà toán học Trung Quốc Tôn Tử (Sun Tzu) đề xuất vào khoảng thế kỷ thứ $3$ đến thứ $5$ sau Công nguyên (không phải Tôn Tử tác giả “Binh Pháp Tôn Tử” nổi tiếng).

Định Lý Số Dư Trung Quốc: Nền Tảng Toán Học Đằng Sau

Khám phá Định lý Sun Tzu

Định lý Số dư Trung Quốc cho phép chúng ta tìm một số chưa biết nếu chúng ta biết số dư của nó khi chia cho một tập hợp các số đã cho, với điều kiện các số chia đó phải là “đôi một nguyên tố cùng nhau” (tức là không có bất kỳ ước số nguyên tố chung nào ngoài $1$). Mặc dù Tôn Tử không chứng minh định lý này một cách chính thức, nhưng sau này, nhà toán học và thiên văn học Ấn Độ Aryabhata đã phát triển một quy trình để giải bất kỳ trường hợp nào của định lý này.

Như Daniel Litt từ Đại học Georgia đã nói: “Định lý Số dư Trung Quốc cung cấp cho bạn một công thức thực sự để tạo ra một con số.”

Giải mã bí mật: Hệ phương trình đồng dư

Để hiểu rõ hơn cách định lý hoạt động, hãy quay lại ví dụ về quân số. Mục tiêu của chúng ta là tìm một số nguyên $X$ (tổng số quân) thỏa mãn các điều kiện sau:

• $X$ chia cho $5$ dư $3$.
• $X$ chia cho $8$ dư $7$.
• $X$ chia cho $9$ dư $2$.

Trong toán học, đây được gọi là một hệ phương trình đồng dư, và được viết như sau:

$$X \equiv 3 \pmod{5}$$
$$X \equiv 7 \pmod{8}$$
$$X \equiv 2 \pmod{9}$$

Bây giờ, chúng ta sẽ giải từng bước:

Bước 1: Giải hai điều kiện đầu tiên

Điều kiện đầu tiên, $X \equiv 3 \pmod{5}$, có nghĩa là $X$ có thể là bất kỳ số nào trong dãy $3, 8, 13, 18, 23, 28, 33, 38, …$ (các số này khi chia cho $5$ đều dư $3$).

Điều kiện thứ hai, $X \equiv 7 \pmod{8}$, có nghĩa là $X$ có thể là bất kỳ số nào trong dãy $7, 15, 23, 31, 39, 47, …$ (các số này khi chia cho $8$ đều dư $7$).

Bây giờ, chúng ta cần tìm một số xuất hiện trong cả hai danh sách. Quan sát, chúng ta thấy số $23$ là số nhỏ nhất thỏa mãn cả hai điều kiện này.

Để tìm các số khác cũng thỏa mãn cả hai điều kiện, chúng ta lấy tích của hai số chia là $5$ và $8$, tức là $5 \times 8 = 40$. Bất kỳ số nào có dạng $23 + 40 \times K$ (với $K$ là số nguyên bất kỳ) cũng sẽ thỏa mãn cả hai đồng dư. Ví dụ: $23, 63, 103, 143, 183, …$ Số nhỏ nhất là $23$.

Bước 2: Thêm điều kiện thứ ba

Bây giờ, chúng ta bổ sung điều kiện thứ ba: $X \equiv 2 \pmod{9}$.

Chúng ta sẽ kiểm tra các số trong danh sách đã thỏa mãn hai điều kiện đầu tiên: $23, 63, 103, 143, 183, 223, 263, …$

• $23 \div 9 = 2$ dư $5$.
• $63 \div 9 = 7$ dư $0$.
• $103 \div 9 = 11$ dư $4$.
• $143 \div 9 = 15$ dư $8$.
• $183 \div 9 = 20$ dư $3$.
• $223 \div 9 = 24$ dư $7$.
• $263 \div 9 = 29$ dư $2$.

Đây rồi! Số $263$ là số nhỏ nhất thỏa mãn cả ba điều kiện. Nếu chúng ta biết tổng số quân không vượt quá $300$, thì $263$ chính là con số bí mật mà vị tướng quân cần tìm.

Tổng quát hơn, vì $5, 8, 9$ là các số đôi một nguyên tố cùng nhau, nghiệm tổng quát sẽ có dạng $X \equiv 263 \pmod{5 \times 8 \times 9}$, tức là $X \equiv 263 \pmod{360}$.

Khi các “ước số” không còn “nguyên tố cùng nhau”: Bài toán Sao Chổi

Cho đến nay, chúng ta đã sử dụng các số chia (modulus) là các số nguyên tố cùng nhau. Nhưng nếu chúng ta không thể chọn các số chia như vậy thì sao? Ví dụ, hãy xem xét hai sao chổi có chu kỳ quỹ đạo lần lượt là $4$ năm và $10$ năm. Chúng vừa đạt đến điểm cận nhật (điểm gần Mặt Trời nhất) vào các năm $1991$ và $1997$. Làm thế nào để xác định năm tiếp theo chúng sẽ cùng đạt cận nhật?

Định lý Số dư Trung Quốc vẫn có thể giúp ích! Khi các số chia không phải là nguyên tố cùng nhau, thay vì sử dụng bội số của tích của chúng, chúng ta sử dụng bội số của bội số chung nhỏ nhất (LCM) của chúng.

Chúng ta đang tìm một năm bí ẩn, $X$, thỏa mãn hệ phương trình đồng dư sau:

$$X \equiv 1991 \pmod{4}$$
$$X \equiv 1997 \pmod{10}$$

Đầu tiên, chúng ta rút gọn các đồng dư:

• $1991 \div 4 = 497$ dư $3$. Vậy $X \equiv 3 \pmod{4}$.
• $1997 \div 10 = 199$ dư $7$. Vậy $X \equiv 7 \pmod{10}$.

Các số thỏa mãn $X \equiv 3 \pmod{4}$ là: $3, 7, 11, 15, 19, 23, …$

Các số thỏa mãn $X \equiv 7 \pmod{10}$ là: $7, 17, 27, 37, …$

Số nhỏ nhất xuất hiện trong cả hai danh sách là $7$.

Tiếp theo, vì $4$ và $10$ không nguyên tố cùng nhau (ước chung lớn nhất của chúng là $\text{GCD}(4, 10) = 2$), chúng ta cần tìm bội số chung nhỏ nhất của chúng: $\text{LCM}(4, 10) = \frac{4 \times 10}{\text{GCD}(4, 10)} = \frac{40}{2} = 20$.

Vậy nghiệm tổng quát là $X \equiv 7 \pmod{20}$.

Vì chúng ta tìm năm sau $1997$, chúng ta cần tìm $K$ sao cho $X = 20K + 7 \ge 1997$. Giá trị $K$ nhỏ nhất thỏa mãn là $K = 100$.

Khi $K = 100$, $X = 20 \times 100 + 7 = 2007$.

Vậy năm $2007$ là năm đầu tiên sau $1997$ mà cả hai sao chổi cùng đạt cận nhật. Các năm tiếp theo sẽ là $2027, 2047, …$

Vượt Ra Ngoài Chiến Trường: Ứng Dụng Đa Dạng Của Định Lý Số Dư

Ví dụ về sao chổi này chứng minh tính ứng dụng rộng rãi của định lý, không chỉ trong thiên văn học (tính toán lịch cổ) mà còn trong kỹ thuật (chọn kích thước gạch phù hợp cho công trình, có thể đã giúp xây Vạn Lý Trường Thành). Hơn $1.500$ năm sau, nó vẫn là một công cụ hữu ích để giải quyết các vấn đề hiện đại, bao gồm cả mã hóa RSA, giao thức bảo mật chính cho liên lạc trực tuyến.

Sức mạnh của Số học Modulo

Định lý Số dư Trung Quốc còn là nền tảng cho một nhánh cơ bản của lý thuyết số gọi là số học modulo. Đây là cách thực hiện các phép toán trong các hệ thống số nhỏ hơn, giống như chúng ta đã làm trong các ví dụ về quân lính và sao chổi.

Các nhà toán học thường xuyên sử dụng số học modulo để nghiên cứu những câu hỏi sâu sắc nhất trong lĩnh vực của họ. Trong nhiều thế kỷ, một trọng tâm nghiên cứu trong lý thuyết số là xác định khi nào các loại phương trình đa thức như $x^2 + y^2 = z^2$ có nghiệm nguyên. Với bất kỳ phương trình đa thức nào, có vô số sự kết hợp bạn có thể thử, khiến việc tìm kiếm bằng cách thử từng trường hợp là không khả thi.

Nhưng để bắt đầu, bạn có thể thử trả lời câu hỏi trong một hệ thống số học modulo, nơi bạn thực sự có thể kiểm tra mọi giá trị có thể. Có nhiều ví dụ về cách tiếp cận này. Ví dụ, vào thế kỷ $17$, Pierre de Fermat đã thách thức các nhà toán học Anh chứng minh rằng phương trình $y^2 = x^3 – 2$ chỉ có hai cặp nghiệm nguyên: $(3, 5)$ và $(3, -5)$. Hóa ra, các nhà toán học phát hiện ra rằng bước đầu tiên để giải quyết vấn đề này là nghiên cứu bài toán theo modulo $4$, điều này đã cung cấp cho họ một điểm tựa và thiết lập rằng ít nhất, $x$ cần phải là số lẻ.

Trong các trường hợp khác, số học modulo có thể loại trừ khả năng một phương trình đa thức có bất kỳ nghiệm nguyên nào. Nếu bạn không tìm thấy nghiệm trong hệ thống số modulo, bạn có thể chuyển những gì đã học thành các tuyên bố về việc thiếu nghiệm cho cùng một phương trình trong tập hợp tất cả các số nguyên.

“Nếu không có nghiệm theo modulo của một số nguyên tố, thì bạn biết rằng không có nghiệm nào cả,” Litt nói.

Đây là một ví dụ khác về việc hơn $1.000$ năm sau, Định lý Số dư Trung Quốc vẫn cung cấp những manh mối cho những chân lý lớn hơn – khiến nó trở thành một công cụ mạnh mẽ trong toán học, ngay cả khi nó không còn cần thiết để truyền bí mật giữa các vị tướng quân nữa.