孙子定理解析
梅锐仁
一、 特例：在《孙子①算经》中，有“物不知其数”一问：“今有物不知其数。三三数之剩二，五五数之剩三，七七数之剩二，问物有几何？”程大卫②在《算法统宗》中用下列诗句来描述这个问题的算法：三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百零五便得知。其意思是：用70乘3除所得的余数：70×2＝140；用21乘5除所得的余数：21×3＝63；用15乘7除所得的余数：15×2＝30；然后将这三个数加起来：70×2＋21×3＋15×2＝233；最后，233－105－105＝23。这就是所求的数的最小值。70、21、15这三个数的来历如何？有关这个数论里的理论史称“孙子定理”，也叫“余数定理”。二、 数理分析：1、 一个数能被a、b整除，而除以c余1，那么把这个数扩大r倍（暂时定r＜c，至于更大范围的讨论这里避开）以后，仍能被a,b整除，但除以c余r。2、 a1除以p余r，a2、a3、……an能被p整除，那么（a1+a2+a3+……+an）除以p仍余r。3、 满足题目条件的数加上或减去应用过的几个除数（一般均为素数，例上特例的3、5、7）的（最小）公倍数后仍旧满足题目的条件。4、 算法设计理念：某一数m，除以p1余r1，除以p2余r2，除以p3余r3……除以pn余rn，求适合条件的m的最小值。① 设m1除以p1余r1，又能被p2、p3……pn整除，则m1＝q1•p2•p3•p4……pn；设m2除以p2余r2，又能被p1、p3……pn整除，则m2＝q2•p1•p3•p4……pn；设m3除以p3余r3，又能被p1、p2……pn整除，则m3＝q3•p1•p2•p4……pn；……设mn除以pn余rn，又能被p1、p2……pn-1整除，则mn=qn•p1•p2•p3……pn-1。② m1满足除以p1余r1，而m2、m3、m4……mn能被p1整除，∴（m1+m2+m3+m4+……+mn）亦满足除以p1余r1这一条件；m2满足除以p2余r2，而m1、m3、m4……mn能被p2整除，∴（m2+m1+m3+m4+……+mn）亦满足除以p2余r2这一条件；m3满足除以p3余r3，而m1、m2、m4……mn能被p3整除，∴（m3+m1+m2+m4+……+mn）亦满足除以p3余r3这一条件；……mn满足除以pn余rn，而m1、m2、m3……mn-1能被pn整除，∴（mn+m1+m2+m3+……+mn-1）亦满足除以pn余rn这一条件。③ 因此（m1+m2+m3+m4+……+mn）同时满足题目条件，减去这些除数的最小公倍数或某一合适的公倍数，即减去R[p1，p2，p3，p4……pn]以后便得出m的最小值（R为自然数）。④ qi的求法可根据数理分析第一步阐述的规律及视余数的大小去选定，还要对是否满足题目条件进行验证确定，不一定每次都等于余数。⑤ 对特例的算法进行演示：三三数之剩二，先设定一个能同时被5和7整除但被3除却剩2的数，1×35＝35就是了；五五数之剩三，再设定一个能同时被3和7整除但被5除却剩3的数，3×21＝63就是了；七七数之剩二，又设定一个能同时被3和5整除但被7除却剩2的数，2×15＝30就是了。它们的和35＋63＋30＝128。用这个和减去[3，5，7]=105,即128－105＝23为所求。至于程大卫在“三三数之剩二”中用2×70＝140似乎把数字扩大了，大概是为了使第一句诗句赋予一定的意义——“三人同行七十稀”吧，结果要在总和中减去105的2倍才得出结果。 三、 算法流程：某一数m，除以p1余r1，除以p2余r2，除以p3余r3……除以pn余rn。求m值的最小数。① 设定一个qi，令mi＝qi•p1•p2……pi-1•pi+1•pi+2……pn且除以pi余ri，qi视ri的大小而选定，不一定等于余数ri，只要是能满足上面条件的最小数值就是了，则m 满足题设条件；其中每一pi均为素数。② 用m 减去R[p1，p2，p3，……pn]则为所求m的最小值，R为自然数。四、 算法演示：① 有一个数，除以3余2，除以5余3，除以7余5，求这个数的最小值。解：由除以3余2，设定m1＝1×5×7＝35（这里的q1不等于余数2）；由除以5余3，设定m2＝3×3×7＝63；由除以7余5，设定m3＝5×3×5＝75。35＋63＋75＝173，则173－3×5×7＝68为所求。② 有一个数，除以2余1，除以3余2，除以5余4，除以7余3，求这个数的最小值。解：由除以2余1，设定m1＝1×3×5×7＝105；由除以3余2，设定m2＝2×2×5×7＝140；由除以5余4，设定m3＝2×2×3×7＝84（这里q3不等于余数4）；由除以7余3，设定m4＝5×2×3×5＝150（这里的q4不等于余数3）。105＋140＋84＋150＝479，则479－2×（2×3×5×7）＝59为所求。 注：① 孙子，姓孙名武，字长卿，春秋末期齐国人，中国古代著名的军事家。② 程大卫（1533～1606），中国明朝著名数学家，他编纂的《算法统宗》传入日本、朝鲜及东南亚，并对这些国家和地区的数学发展产生了很大的影响。③ 在这个用“余数定理”求导结果的算法中，每一pi是由题设条件既定的，而qi的选定却又富于弹性和艺术性，不一定每次都等于余数ri，以达到题设条件的最小数值为准。如果为了某种特定的需要，像程大卫那样为了第一句诗句赋予一定的意义而扩大若干倍也未尝不可。 2006年3月31日 [ 此帖被mrr523在2013-09-14 08:23重新编辑 ]
