中国余数定理的解题套路

《孙子算经》是重要的古代汉语数学著作，约成书于四、五世纪，也就是大约一千五百年前，作者生平和编年不详。

《孙子算经》下卷第28题“物不知数”为后来的“大衍求一术”的起源，被看作是中国数学史上最有创造性的成就之一，称为 中国余数定理，现引述于下：

今有物不知其数，

三三数之剩二，

五五数之剩三，

七七数之剩二，

问物几何？

（答曰二十三。）

 

一、参考解法

满足第一个条件“三三数之剩二”而能被五、七整除的最小数是：5×7=35，

满足第二个条件“五五数之剩三”而能被三、七整除的最小数是：(3×7)×3=63，

满足第三个条件“七七数之剩二”而能被三、五整除的最小数是：(3×5)×2=30，

那么，上述三个数加起来，就会同时满足三个条件。其和为128。

但它可能不是最小的。

因为三、五、七的最小公倍数是105，小于128，

故所求之最小数为128－105=23。

 

二、回顾

回过头来，不难发现，在式中都乘了各自的余数，而在式中却没有乘相应的余数。

这是因为，(3×7)被五除以及(3×5)被七除都余一，要想达到要求，必须乘以各自的余数。

而式中(5×7)除以三的余数正好为二，就不用再乘以自己的余数了。

为了达到一个统一的要求，显然应向二、三式的形式靠拢。

而“三三数之剩一”又能被五、七整除的最小数是：5×7×2=70，

故“三三数之剩二”又能被五、七整除的较大数是：(5×7×2)×2=70×2=140，

这样算下来，同时满足三个条件的数是140＋63＋30=233，

然后需减两个105，得23。

 

三、神秘古诗呼之欲出

至此，【明】程大位《算法统宗》中那首神秘的古诗就呼之欲出了：

三人同行七十稀，

五树梅花廿一枝，

七子团圆月正半，

除百零五便得知。

这称为诗歌形式的孙子定理或中国余数定理。

可见，如果没有一个统一的规范要求，也就没有“三人同行七十稀”这样美妙的诗句了。

 

四、神秘古诗的特定翻译

找出一个能被5及7整除而除以3余1的数，然后再乘上除以3的给定余数；

找出一个能被3及7整除而除以5余1的数，然后再乘上除以5的给定余数；

找出一个能被3及5整除而除以7余1的数，然后再乘上除以7的给定余数；

上述三个数之和分别除以三、五、七肯定符合要求，但可能不是最小的正整数；

从三个数之和中减去三、五、七的最小公倍数105，直到最小即为所求。

（上述问题，算式是70×2＋21×3＋15×2=233，233－105×2＝23，故最小的正整数解是 23。）

 

五、讨论

1、固定除数三、五、七不变，余数可以为零

如：

今有物不知其数，

三三数之剩一，

五五数之剩〇，

七七数之剩4，

问物几何？

（上述问题，算式是70×1＋21×?×0＋15×4=130，130－105＝25，故最小的正整数解是 25。）

又如：

今有物不知其数，

三三数之剩〇，

五五数之剩〇，

七七数之剩4，

问物几何？

（上述问题，算式是0＋0＋15×4=60，故最小的正整数解是 60。）

显然，如果三个条件都为〇，那就是求最小公倍数了。形式上可以记作：0＋105=105。

 

2、如果将除数改作三、五、八

今有物不知其数，

三三数之剩二，

五五数之剩三，

八八数之剩二，

问物几何？

按照上述问题的套路有：

满足第一个条件而能被五、八整除的数是：(5×8)×2=40×2=80

满足第二个条件而能被三、八整除的数是：(3×8×4)×3=96×3=288

满足第三个条件而能被三、五整除的数是：(3×5×7)×2=105×2=210

那么，上述三个数加起来，就会同时满足三个条件。

其和为578。但它可能不是最小的。

因为三、五、八的最小公倍数是120，小于578，

故所求之最小数为578－480=98。

那首神秘的古诗，不妨修改如下：

三人同行卌不惑，

五树梅花九六枝，

八子团圆百〇五，

除百二十便得知。

 

3、如果将除数改作三、五、九

今有物不知其数，

三三数之剩二，

五五数之剩三，

九九数之剩二，

问物几何？

按照上述问题的套路有：

满足第一个条件而能被五、九整除的数是：5×9×？，总能被三整除。不能满足条件。

满足第二个条件而能被三、九整除的数是：(3×9×3)×3=81×3=243

满足第三个条件而能被三、五整除的数是：3×5×?，15的倍数除以九，如果有余数，只能是六、三、〇，余一或余二不可能。

那么此题就无解了吗？继续探索。

 

考虑到满足“九九数之剩二”的数，必然满足“三三数之剩二”，故问题可简化为：

今有物不知其数，

五五数之剩三，

九九数之剩二，

问物几何？

仍循上述问题的套路有：

满足第一个条件而能被九整除的数是：(9×4)×3=108。

满足第二个条件而能被五整除的数是：(5×2)×2=20。

那么，上述两个数加起来，就会同时满足两个条件。

其和为128。但它可能不是最小的。

因为五、九的最小公倍数是45，小于128，

故所求之最小数为128－45×2=38。

当然，这个数也满足“三三数之剩二”的条件。

由此可见，不是套路有问题，而是除数须互质。

通俗说，就是消除互相的包容、叠加或冗余，使所列条件互相独立。

 

六、数鸡蛋问题

社会上流传的数鸡蛋问题最终可以归结为下述《孙子算经》的形式。

（具体简化过程见附录。）

今有物不知其数，

五五数之剩一，

八八数之剩一，

六十三、六十三数之剩〇

问物几何？

按照上述问题的套路有：

满足第一个条件而能被八、六十三整除的数是：(8×63×4)×1=2016。

满足第二个条件而能被五、六十三整除的数是：(5×63×3)×1=945

满足第三个条件而能被五、八整除的数是：(5×8×？)×0=0

那么，上述三个数加起来，就会同时满足三个条件。

其和为2961。但它可能不是最小的。

因为五、八、六十三的最小公倍数是2520，小于2961，

故所求之最小数为2961－2520=441。

 

七、结语

余数问题多，古诗套路精。

除数须互质，否则先合并。

条件三以下，除数大不惊。

整除不忌讳，同余最欢迎。

【附录】数鸡蛋问题及其简化

一筐鸡蛋：

1个1个拿，正好拿完。

2个2个拿，还剩1个。

3个3个拿，正好拿完。

4个4个拿，还剩1个。

5个5个拿，还剩1个

6个6个拿，还剩3个。

7个7个拿，正好拿完。

8个8个拿，还剩1个。

9个9个拿，正好拿完。

问筐里最少有多少个鸡蛋？

 

这个问题多达九个已知条件，很多人一看就懵了，不知道该从哪里下手。其实，这九个条件中有些是凑数的废话，有些是被兼容的，所以第一步就是要删除多余的条件，然后从保留的条件里提取有用的信息，从而找到解决问题的钥匙。

“1个1个拿，正好拿完。” —— 这是一句正确的废话。

“2个2个拿，还剩1个。” —— 说明总数是奇数。此条可被“8个8个拿，还剩1个”涵盖。

“3个3个拿，正好拿完。” ——该条件已经被“9个9个拿，正好拿完”涵盖。

“4个4个拿，还剩1个 。” —— 该条件已经被“8个8个拿，还剩1个”涵盖。

“6个6个拿，还剩3个。” ——此条可以分解为“2个2个拿，还剩1个。”与“3个3个拿，正好拿完。”

“7个7个拿，正好拿完。”

“9个9个拿，正好拿完。” ——7、9互质，说明这个数是63的倍数。

 

所以问题可为：

今有物不知其数，

五五数之剩一，

八八数之剩一，

六十三、六十三数之剩〇，

问物几何？

 

根据头两行，这个数减一，能被四十整除，故此数个位为“1”。

又能被六十三整除，而三七二十一，故有63*7=441。

验证正确。

 

如果问题改为：

能被63整除，且

除以5余4；（末位为9或4）

除以8余1。（必为奇数）

求这个数。

 

由是，此数末位必为9，而63的倍数需为 3/13/23/……

经试，63*23=1449。

验证正确。