为什么孙子剩余定理可用于计算机编码

孙子剩余定理过去曾称作中国剩余定理，它是中国古代数学中的一项重大成就，其内容属于数论中的一次同余数组的解法。定理的最初内容出现在《孙子算经》一书中，是针对著名的“孙子问题”，即“物不知数问题”所提出的一种解法。物不知数问题的大意是：有物不知其数，三个一数余二，五个一数余三，七个一数余二，问该物总数共有多少？后来，这一问题成为广泛流传的一种数学游戏，被称为“韩信点兵”、“鬼谷算”等。

在数学上，常有古老的数学知识放射出新的光彩的现象。孙子剩余定理这一古老的知识，现今在计算机编码方面也找到了新的用途。

物不知数问题的答案可以有许多，如23，128，233，…它们之间都相差105（即3×5×7），但在105之内的解是唯一的：23。为了便于说明孙子剩余定理在计算机编码中的应用，我们把物不知数问题简化为：三三数之余二，五五数之余三，求物数。这个解答不难求出，是8，23，38，53，…它们之间都相差15（即3×5）。而在15之内解是唯一的：8。

换一下数据，另编一道题：三三数之余一，五五数之余二，求物数。其答案为7，22，37，…并且在15之内的解也是唯一的：7。

这样的题目可以编出多少个呢？三三数之，余数可以是0、1、2，共三种；五五数之，余数可以是0、1、2、3、4，共五种，合起来共3×5，等于15种。就是说，可以编15个这样的题目。它们的答案各不相同，而且在15之内又都是唯一的，可见，这15道题的答案正巧分别等于1，2，3，…，15。

现在，把1，2，3，…，15这些数一一填入一个3×5的方格纸的方格内。比如8，因为它是“三三数之余二”，所以填在第二行；又因为它是“五五数之余三”，所以又要填在第三列。按照这个方法，可以将1，2，3，…，15一一填入各个方格内（如下图）。

任何一台计算机，都有一定的“字长”。字长就是它所能处理的数的最大位数。那么，当我们要利用计算机来处理一个位数超过计算机额定字长的数据时，该怎么办呢？通常的办法是将这个大数用两个小一点的数来表示。最简单的方法是把大数分成两段，如3517，可以分成35和17两个小一点的数。但是这样做，计算机在进行运算时困难较大，因而一般认为是不可取的。

利用孙子剩余定理，却可以将一个大数用两个较小的数表示（或编码），并且使计算机运算起来十分方便。且看前面说过的3×5的方格纸，1，2，3，…，15已分别填在里面。8填在第二行、第三列，“8”这个较大的数，可以用两个较小的数2和3来表示（或编码）；15填在第三行、第五列，“15”这个较大的数，可以用两个较小的数3和5表示（或编码）；……这样一来，如果我们的计算机原来只能处理5以内的数，现在就可以处理1到15的数了。

这样编码后，运算方便不方便呢？我们说，十分方便。比如，在第二列中取一个数2，第三列中取一个数3，它们的积是6，积在第一列，而且，第二列中的任何数与第三列中的任何数的积必定在第一列（当积超出15时，可以按前面说过的方法继续将16，17，…填在3×5的方格纸中）。

这是什么缘故呢？原来，在同余式理论中，如果

x₁≡x₂（mod5），y₁≡y₂（mod5），

（意思是x₁和x₂被5除以后，有相同的余数；y₁和y₂被5除以后有相同的余数）那么

x₁y₁≡x₂y_2（mod5），

也就是x₁y₁和x₂y₂被5除以后有相同的余数。这个性质可以在介绍数论的书上找到。利用这个性质就可以说明，为什么第二列的数与第三列的数的积总在第一列。我们另取一个在第二列的数a，它必定与2一样，被5除以后有相同余数，即

a≡2（mod5）。

同理，另取第三列中的数b，必有

b≡3（mod5）。

所以

ab≡6（mod5）。

我们已经知道6在第一列中，所以ab在第一列中。

对行也有相同的结果。

这样一来，计算机在进行大数的运算时就十分方便。譬如说，我们要做乘法2×6，注意到其中的乘数6已超过5，对我们前面所说的那个“微型”计算机来说，已是大数，因此我们首先得把每个数都用两个小数来表示（或编码）：

2——（第二行、第二列）；

6——（第三行、第一列）。

可以证明，第二行与第三行中的数的积必在第三行；第二列与第一列中的数的积必在第二列。这样，积2×6必可以用两个较小的数3与2表示（或编码）。从表中一查，位于第三行与第二列交叉点上的数是12，所以2×6的积为12。

你看，先把两个大数分别表为两个较小的数（表中的行、列序号）；然后根据两个行的序号定出两个大数积的行的序号，根据两个列的序号定出积的列序号；最后，根据积的行、列序号在表中查出积的值，这样计算机就可以很方便地求出大数的乘积来了。这说明利用孙子剩余定理编码是很有好处的。