简介

物不知数

详细解法

意义

简介

中国剩余定理，又称为中国余数定理、孙子剩余定理，古有“韩信点兵”、“孙子定理”、“鬼谷算”、“隔墙算”、“剪管术”、“秦王暗点兵”、“物不知数”之名，是数论中的一个重要命题。

物不知数

在中国古代著名数学著作《孙子算经》中，有一道题目叫做“物不知数”，原文如下：

有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？

即，一个整数除以三余二，除以五余三，除以七余二，求这个整数。中国数学家秦九韶于1247年做出了完整的解答，口诀如下：

三人同行七十希，五树梅花廿一支，七子团圆正半月，除百零五使得知

这个解法实际上是，首先利用秦九韶发明的大衍求一术求出5和7的最小公倍数35的倍数中除以3余数为1的最小一个70（这个称为35相对于3的数论倒数），3和7的最小公倍数21相对于5的数论倒数21，3和5的最小公倍数15相对于7的数论倒数15。然后70X2+21X3+15X2=233

233便是可能的解之一。它加减3、5、7的最小公倍数105的若干倍仍然是解，因此最小的解为233除以105的余数23。

附注：这个解法并非最简，因为实际上35就符合除3余2的特性，所以最小解是：35X1+21X3+15X2-3X5X7=128-105=23 最小解加上105的正整数倍都是解。

详细解法

该问题可以用初等数论中的同余方程组的求解问题。利用同余的符号，可以将上述问题转化为下面的同余方程组：

x≡2(mod 3)；

x≡3(mod 5)；

x≡2(mod 7)；

不难看出上述同余方程组的解并不唯一，因为如果x是一个解，则x+3×5×7×k=x+105k也是该同余方程组的一个解，其中的k可以是任意整数。事实上，从3，5，7两两互质可知上述同余方程组的任意两个解相差105的倍数。所以，一旦求出“最小正整数解”x0，则每个解均可表示为x=x0+105k。

如何求出上述同余方程组的一个解呢？我们的祖先聪明的把问题转化为以下三个非常特殊的同余方程组的求解

a≡1(mod 3)； b≡0(mod 3)； c≡0(mod 3)；

a≡0(mod 5)； b≡1(mod 5)； c≡0(mod 5)；

a≡0(mod 7)； b≡0(mod 7)； c≡1(mod 7)；

显然，如果求出了a，b，c的一组值，则2a+3b+2c就是原同余方程组的一个解，再把这个解除以105，则相应的余数即为所求的最小整数解。经过简单计算可知a可以取70，b可以取21，c可以取15。所以2a+3b+2c=233，除以105后得余数为23，这就是所求的最小正整数解。

意义

“物不知数”的解法实际上给出了求解一般同余方程组的方法。设m1，m2，…，mi为两两互质的正整数，a1，a2，…，ak为任意整数，则同余方程组

x≡a1(mod m1)；

x≡a2(mod m2)；

……

x≡ai(mod mi)；

总有整数解，并且它的全部解可模仿上述方法得到。