Vì sao định lý thặng dư Trung Quốc có thể dùng để mã hóa máy tính?

Chúng ta đã biết đến định lý thặng dư Trung Quốc, tức vấn đề Hàn Tín điểm binh. Đây là một thành tựu quan trọng trong toán học cổ Trung Quốc, có nội dung thuộc về việc giải dãy đồng dư bậc nhất trong lý thuyết số. Hiện nay, người ta đã tìm ra công dụng mới của kiến thức cổ xưa này trong việc mã hóa máy tính.

Đáp án của bài toán Hàn Tín điểm binh có thể có rất nhiều, giữa các đáp án lại chênh nhau 105, tức 3 x 5 x 7; nhưng đáp án trong phạm vi 105 thì chỉ có một. Bây giờ, chúng ta hãy giản hóa vấn đề: những số nguyên nào khi chia 3 dư 2, chia 5 dư 3? Không khó để tìm ra các số 8, 23, 38, 53,..., giữa chúng chênh nhau 15, tức 3 x 5. Còn đáp án trong phạm vi 15 chỉ có một: số 8. Vậy với dạng đề bài như vậy có thể có bao nhiêu bài toán? Khi chia 3, số dư có thể là 0, 1, 2, tổng cộng 3 loại; khi chia 5, số dư có thể là 0, 1, 2, 3, 4, tổng cộng 5 loại. Hợp lại là 3 x 5, tức 15 loại. Nghĩa là có thể có 15 đề bài như vậy, đáp án không giống nhau, và đáp án trong phạm vi 15 thì chỉ có một. Có thể thấy đáp án của 15 đề bài này vừa khéo tương ứng với các số 1, 2, 3,..., 15.

Bây giờ, hãy điền 15 số này vào một hình vuông 3 hàng 5 cột, tức 3 x 5, sao cho hàng ngang là các số có số dư khi chia cho 3, còn hàng dọc là các số có số dư khi chia cho 5. Ví dụ, 8 là số chia cho 3 dư 2, nên điền vào hàng thứ hai; nó lại là số chia cho 5 dư 3, nên điền vào cột thứ ba.

Bất cứ máy tính nào cũng có một độ dài từ, tiếng Anh là word length, nhất định. Độ dài từ chính là con số, tức digit, lớn nhất mà máy tính có thể xử lý được. Vậy khi cần dùng máy tính để xử lý một dữ liệu có các số vượt quá độ dài từ đã định thì làm thế nào? Biện pháp thông thường là biểu thị số lớn ấy bằng hai số nhỏ hơn. Cách đơn giản nhất là chia số lớn thành hai đoạn, chẳng hạn chia 3517 thành hai số nhỏ hơn là 35 và 17. Nhưng làm như vậy thì thao tác của máy tính sẽ khó hơn, nên người ta thường cho rằng không nên áp dụng.

Sử dụng định lý thặng dư Trung Quốc có thể biểu thị, hoặc mã hóa, một số lớn bằng hai số nhỏ hơn, đồng thời khiến máy tính thao tác rất thuận tiện. Hãy nhìn lại hình vuông 3 x 5 nói trên: số 8 được xếp ở hàng 2 cột 3, nên có thể biểu thị bằng 2 và 3; tương tự, 15 có thể biểu thị bằng 3 và 5... Nếu máy tính vốn chỉ có thể xử lý các số trong phạm vi 15, thì nhờ cách này nó vẫn có thể xử lý thuận tiện những số được mã hóa tương ứng. Hơn nữa, sau khi mã hóa, thao tác cũng rất dễ dàng.

Ví dụ, lấy số 2 ở cột hai, lấy số 3 ở cột ba, tích của chúng là 6, nằm ở cột một. Hơn nữa, tích của bất cứ số nào ở cột hai với bất cứ số nào ở cột ba cũng nhất định nằm ở cột một, khi tích lớn hơn 15 thì có thể tiếp tục điền 16, 17... vào hình vuông 3 x 5 theo phương pháp đã nói trên.

Vì sao lại như vậy? Thì ra, trong lý thuyết đồng dư, nếu

tức x1 và x2 có số dư giống nhau sau khi trừ đi 5; y1 và y2 cũng có số dư giống nhau sau khi trừ đi 5, thì

cũng tức là x1y1 và x2y2 có số dư giống nhau sau khi trừ đi 5. Sử dụng tính chất này, có thể chứng minh rằng tích của các số cùng cột với 2 và 3, tức cùng hàng có số dư giống nhau sau khi trừ đi 5, phải có đồng dư 6, nghĩa là ở cùng một cột.

Hàng đối cũng có kết quả tương tự.

Cứ như vậy, máy tính khi thao tác với các số lớn sẽ rất thuận tiện. Chẳng hạn, nếu muốn làm phép nhân 2 x 6, trước tiên phải tiến hành mã hóa hai số:

2 - (hàng hai, cột hai)

6 - (hàng ba, cột một)

Có thể chứng minh, tích của số ở hàng hai cột ba phải ở hàng ba; tích của số ở hàng hai cột một phải ở hàng hai. Thế là, tích có thể dùng 3 và 2 để biểu thị, hoặc mã hóa. Tra trong bảng sẽ biết tích của 2 x 6 là 12.

Nói cách khác, trước tiên biểu thị số lớn bằng hai số nhỏ, tức ký hiệu thứ tự hàng và cột trong bảng; sau đó căn cứ vào ký hiệu thứ tự của hai hàng để xác định ký hiệu thứ tự hàng của tích hai số lớn, căn cứ vào ký hiệu thứ tự của hai cột để xác định ký hiệu thứ tự cột của tích; cuối cùng dựa vào ký hiệu hàng và cột trong bảng để tra ra trị số của tích. Nhờ vậy, máy tính sẽ dễ dàng tìm được tích của các số lớn.

Vì thế, việc sử dụng định lý thặng dư Trung Quốc để mã hóa cho máy tính là hết sức hữu ích; trí tuệ của tổ tiên chúng ta đã tiếp tục được thể hiện trong khoa học kỹ thuật hiện đại.