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, đó là một thành tựu quan trọng trong toán học Trung Quốc cổ đại, với nội dung thuộc về giải pháp dãy đồng dư một lần trong lí thuyết số. Hiện nay, người ta đã tìm ra công dụng mới của thứ kiến thức cổ xưa này trong việc mã hóa máy tính.

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

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

Bất cứ một máy tính nào cũng đều có một độ dài từ (word length) nhất định. Độ dài từ chính là con số (digit) lớn nhất mà máy tính có thể xử lí được. Vậy thì, khi chúng ta cần sử 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. Biện pháp đơn giản nhất là chia số lớn thành hai đoạn, như có thể chia 3517 thành hai số nhỏ hơn là 35 và 17. Nhưng làm như vậy thì máy tính khi thao tác sẽ khó hơn, cho nên người ta thường cho là không nên áp dụng.

Sử dụng định lí thặng dư của 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 lại khiến cho máy tính thao tác hết sức thuận tiện. Chúng ta hãy nhìn lại hình vuông 3x5 ở trên, 8 được sắp và hàng 2 cột 3, 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 như máy tính của chúng ta vốn chỉ có thể xử lí được các số trong vòng 15, thì hiện tại có thể xử lí được đến 15. Hơn nữa, sau khi mã hóa như vậy thao tác cũng sẽ rất thuận tiện.

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 là nằm ở cột một (khi tích lớn hơn 15, có thể tiếp tục điền 16, 17... vào trong hình vuông 3 x 5 dựa theo phương pháp nói trên).

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

(tức x1 và x2 có số dư giống nhau sau khi trừ đi 5; y1 và y2 có số dư giống nhau sau khi trừ đi 5), vậy

cũng tức là x1y1 và x2 y2 có số dư giống nhau sau khi trừ đi 5. Sử dụng tính chất này thì sẽ chứng minh được, tích của số (cùng hàng có số dư giống nhau sau khi trừ đi 5) cùng cột với 2 và 3 phải có đồng dư 6, tức ở cùng 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, chúng ta muốn làm phép nhân 26, thì trước tiên phải tiến hành mã hóa cho 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 được tích của 26 là 12.

Cũng có nghĩa là, đầu tiên biểu thị số lớn bằng hai số nhỏ (có kí hiệu thứ tự hàng, cột trong bảng); sau đó căn cứ theo kí hiệu thứ tự của hai hàng để định ra kí hiệu thứ tự hàng của tích hai số lớn, căn cứ theo kí hiệu thứ tự của hai cột để định ra kí hiệu thứ tự cột của tích; cuối cùng căn cứ theo kí hiệu thứ tự hàng và cột trong bảng sẽ tra ra được trị số của tích. Như vậy, máy tính sẽ rất dễ dàng tìm ra được tích số của các số lớn.

Vì thế, việc sử dụng định lí thặng dư của Trung Quốc để tiến hành 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 đã được thể hiện thêm trong khoa học kĩ thuật hiện đại.

Làm thế nào sắp xếp công nhân bảo dưỡng sửa chữa hợp lí nhất?

Trên đây chúng ta đã nghiên cứu vấn đề bố trí số công nhân bảo dưỡng, sửa chữa cho một nhà máy, bây giờ chúng ta nghiên cứu cách sắp xếp để cho các...

Tại sao nghe tiếng nói của mình trong băng ghi âm lại cảm thấy xa lạ?

Nếu bạn ghi âm lại tiếng nói của mình sau đó mở ra nghe, bạn sẽ cảm thấy tiếng nói đó xa lạ, dường như không phải tiếng nói của chính mình. Tại sao lại như vậy?

Vì sao con người không thể sống trong môi trường tuyệt đối không có tiếng động?

Dân cư sống ở thành phố đều mong có một môi trường ít tiếng động. Tiếng ồn đã trở thành vấn đề ô nhiễm rất lớn của thành phố.

Động vật chơi đùa có phải chỉ là để vui hay không?

Trong xã hội loài người, chơi đùa sẽ mang lại rất nhiều niềm vui cho chúng ta, đặc biệt là trẻ em, hầu như hằng ngày đều không thể rời xa trò chơi. Thực ra không chỉ có loài người mà nhiều loài động vật cũng rất thích chơi trò chơi.

Tại sao bề mặt bên ngoài toà nhà Ngân hàng Trung Quốc ở Hồng Kông có rất nhiều hình tam giác?

Dải đất dọc theo bờ biển từ Loan Tử đến Trung Hoàn ở Hồng Kông là một trong những nơi tập trung các cơ quan tài chính tiền tệ thương nghiệp của Hồng...

Vì sao có thể lợi dụng rừng để làm sạch nước thải?

Một đường ống từ Oasinhtơn thông ra rừng ngoại ô. Nước phế thải của các nhà máy đi theo đường ống này đến cánh rừng, sau đó nhiều vòi phun đặc biệt...

Vì sao phương pháp thay thế dần ngày càng tỏ ra quan trọng?

Thế nào là phương pháp thay thế dần? Trước hết ta giải phương trình x2= 2. Thế chẳng phải nghiệm của phương trình là √2 sao? Không sai.

Thế nào là "thực phẩm xanh"?

Thập kỉ 60 của thế kỉ XX nền nông nghiệp thế giới đã phát sinh một cuộc cách mạng kĩ thuật. Phân hoá học, thuốc bảo vệ thực vật, thuốc kích thích sinh...

Tại sao vệ tinh địa tĩnh có thể đứng yên?

Đứng ở một nơi nào nếu ném một quả cẩu theo chiều nằm ngang, do lực hấp dẫn của Trái đất, quả cẩu sẽ bay theo một đường cong và nhanh chóng rơi xuống...