孙子定理.doc

孙子算经l “鸡兔同笼”孙子算经共三卷，完成于公元四-五世纪。卷下第31题，是后世“鸡兔同笼”题的始祖，后来传到日本，变成“鹤龟算”。书中是这样叙述的：“今有鸡兔同笼，上有三十五头，下有九十四足，问鸡兔各几何？这四句话的意思是：有若干只鸡兔同在一个笼子里，从上面数，有35个头；从下面数，有94只脚。求笼中各有几只鸡和兔？ 趣题1：巍巍古寺在山林，不知寺内几多僧。三百六十四只碗，看看用尽不差争。三人共食一碗饭，四人共吃一碗羹。请问先生明算者，算来寺内几多僧？l “荡杯问题”“今有妇人河上荡杯。津吏问曰：杯何以多？妇人曰：有客。津吏曰：客几何？妇人曰：二人共饭，三人共羹，四人共肉，凡用杯六十五。不知客几何？” “术曰：置六十五杯，以一十二乘之，得七百八十，以十三除之，即得”。 这里告诉我们这次洗碗事件，要处理的是65个碗共有多少人的问题。其中有能了解客数的信息是2人共碗饭，3人共碗羹，4人共碗肉。通过这几个数值，很自然就能解决客数问题。因为客数是固定值，因此将其列成今式为N/2+N/3+N/4=65，易得客数六十人。l “孙子定理”（中国剩余定理-一次同余论）孙子算经具有重大意义的是卷下第26题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？答曰：二十三” 这个问题也被称为“物不知数”问题。西方数学史将其称为“中国剩余定理”（Chinese remainder theorem）。与上面的荡杯问题相比较，可以发现主要区别在于这里出现了余数，而不是整除。此题相当于求不定方程组N=3x+2,N=5y+3,N=7z+2 -三个方程式，4个未知数，比较难解。孙子算经给出了算法：N=702+213+1522105=23。 这里105是模数3、5、7的最小公倍数。这里给出的是符合条件的最小正整数。对于一般余数的情形，只要把上述算法中的余数2、3、2分别换成新的余数就行了。以R1、R2、R3表示这些余数，那么孙子算经相当于给出公式N=70R1+21R2+15R3p105（p是整数）。孙子算法的关键，在于70、21和15这三个数的确定：这三个数可以从最小公倍数M=357=105中各约去模数3、5、7后，再分别乘以整数2、1、1而得到。70是5和7的公倍数，且被3除余1；21是3和7的公倍数，且被5除余1；15是3和5的公倍数，且被7除余1.在这样的条件下，任意一个系数乘以对应余数所得的积，被对应出书除后所得的余数恰好等于对应余数，且该积仍然能被其他两个除数整除，因此三个积相加并不相互影响各自被对应出书除后所得的余数。即70R1+21R2+15R3是被3除余R1，被5除余R2，被7除余R3的数。应用上述推理，可以完全类似地把孙子算法推广到一般情形：设有一数N，分别被两两互素的几个数a1、a2、an相除得余数R1、R2、Rn，即表示为NRi（mod ai），（i=1、2、n），只需求出一组数K，使满足1（mod ai）（i=1、2、n），那么适合已给一次同余组的最小正数解是（P是整数，M=a1a2an），这就是现代数论中著名的剩余定理。如上所说，它的基本形式已经包含在孙子算经“物不知数”题的解法之中。不过孙子算经没有明确地表述这个一般的定理。 上述的孙子算法一般情况四年级暂不要求。现在我们掌握的具体的解题思路如下：先从3和5、3和7、5和7的公倍数中相应地找出分别被7、5、3除均余1的较小数15、21、70 ( 注释:此步又称为求模逆运算,利用扩展欧几里得法并借助计算机编程可比较快速地求得。对于很小的数，可以直接死算 ）。即157=2余1，215=4余1，703=23余1.再用找到的三个较小数分别乘以所要求的数（N）被7、5、3除所得的余数的积连加，152+213+702=233. 最后用和233除以3、5、7三个除数的最小公倍数.233105=2余23，这个余数23就是合乎条件的最小数.以上三个步骤适合于解类似孙子问题的所有问题. l 韩信点兵相传汉高祖刘邦问大将军韩信统御兵士多少，韩信答曰：每3人一列余1人、5人一列余2人、7人一列余4人、13人一列余6人。刘邦茫然而不知其数。例题：假设兵不满一万，每5人一列、9人一列、13人一列、17人一列都剩3人，则兵有多少？首先我们先求5、9、13、17之最小公倍数9945（注：因为5、9、13、17为两两互质的整数，故其最小公倍数为这些数的积），然后再加3，得9948（人）。习题1. 一个数除以3余2，除以5余3，除以7余4，问满足条件的最小自然数_.解答:采用中国剩余定理：3,5的公倍数 3,7的公倍数 5,7的公倍数15 21 3530 42 7045 63 10560 84 140 除以7余4的 除以5余3 除以3余2分别是：60 63 35可见60+63+35=158满足我们的条件，但不是最小的自然数，处理方法就是减去最小公倍数的若干倍，使结果在最小公倍数之内。所以答案为：158-105=53。习题2：一条长长的阶梯，如果每步跨 2 级，那么最后余 1 级；如果每步跨 3 级，那么最后余 2 级；如果每步跨 5 级，那么最后余 4 级；如果每步跨 6 级，那么最后余 5 级；只有当每步跨7级时，最后才刚好走完.问这条台阶最少有 多少 级？答案：如果每步跨 2 级，那么最后余 1 级；可知 是个奇数如果每步跨 3 级，那么最后余 2 级；可知+1就是3的整数倍如果每步跨 5 级，那么最后余 4 级；可知尾是4或9.但是是个