《“韩信点兵”与中国的剩余定理-》课件1-优质公开课-人教B版选修3-1

1、2.2 “韩信点兵” 与中国的剩余定理 人教B版数学选修3-1数学史选讲2.2 “韩信点兵” “韩信点兵”与中国的剩余定理 从“鬼谷算”的猜岁数游戏谈起猜谜语这种民间游戏，在中国有几千年的历史了。可是你知道不知道还有一种猜岁数的游戏在一千多年前也曾是中国人民的一种游戏？“韩信点兵”与中国的剩余定理 从“鬼谷算”的猜岁数游戏谈起 让我们借想像的羽翼飞到那古老的年代，飞到那位于富庶肥沃的关中平原，那诗经所说：“径以渭蜀”的径水、渭水流域上的古城长安。长安是个像杜甫的诗歌所描写的：“渔阳豪侠地，击鼓吹笙竽，云帆转辽海，粳稻来东吴。越罗与楚练，照耀与台躯”一个很热闹繁华的城市。 让我们借想像的羽翼飞到

2、那古老的年代，飞到那位于富庶肥我们不单听到吹竽鼓瑟、击筑弹琴，也见到斗鸡走犬。而位于大街的酒家，高朋满座。最热闹的是靠南城门的墙脚地方，只见许多人围绕在一个竹竿高挂上写“鬼谷神算”的布条下。挤进去看，我们看到一个有仙风道骨模样的老人对另一位老观众说：“大爷不需告诉我岁数，只需讲你的岁数除以二、三、五后的余数是多少，就可以了。”我们不单听到吹竽鼓瑟、击筑弹琴，也见到斗鸡走犬。而位于大街的“用二除嘛，余一；用三除嘛，也是余一；用五除嘛是余三。”只见算命先生摆弄一下竹筹，就说：“大爷今年73岁了，有道是人生七十古来稀，大爷童颜鹤龄，龙马精神，真是有福。”他算对了，是怎么样算出来呢？“用二除嘛，余一；

3、用三除嘛，也是余一；用五除嘛是余三。”只见同余的概念首先让我介绍德国数学家高斯在200年前想出的一个数学上很重要的概念：“同余” .给定一个正整数n，我们说两个数a、b是对模n同余，如果ab是n的倍数。用符号ab（mod n）来表示。同余的概念首先让我介绍德国数学家高斯在200年前想出的一个数比方说：7，4，是对模3同余，因为74=3。16，52是对模6同余，因为1652=366（6）。23，13是对模2，模5同余，因为231310=25.写成数学式子是74（mod 3），1652（mod 6），2313（mod 2）或 2313（mod 5）比方说：7，4，是对模3同余，因为74=3。 我们

4、现在令Z表示所有的整数集合，给定一个正整数n，我们看同余究竟有什么性质？ 首先，对于任何整数a ，我们恒有aa（mod n）因为aa00n，以上的性质就是“同余具有自反性。 其次，如果ab（mod n），则一定有ba（mod n）因为由ab（mod n），我们得ab=nk，k是一个整数， 我们现在令Z表示所有的整数集合，给定一个正整数n 因此ba=（ab）n（k），即ba（modn）。我们说“同余具有对称性”。 另外如果有ab（mod n），bc（mod n）， 则我们可以得到ac（mod n）。 这就是“同余具有传递性。 因此ba=（ab）n（k），即ba（m让我们看看下面的例子：例1取n2

5、，则我们把整数分成偶数或奇数，就是02=0，2，4，6，2k，包含所有偶数。12=1，3，（2k+1)，包含所有的奇数。让我们看看下面的例子：例1取n2，则我们把整数分成偶数或例2 . 取n3，则03=，9，6，3，0，3，6，9，13=，8，5，2，1，4，7，10，23=，7，4，1，2，5，8，11，现在让我问一个问题：“什么数被2除余1？”我想你一定会回答：是所有的奇数，奇数一般可以用2k1来表示k0，1，2，。这就是在12的数。例2 . 取n3，则现在让我问一个问题：“什么数被2除余1现在让我再问一个问题：“什么数被3除余2？”我想你一定会回答：所有形如3k2的数，这里k可以等于0，

6、1，2，这就是在23里的数。这两个问题都是很容易。现在让我们把这两个问题合成一个问题：“什么数被2除余1，被3除余2？”现在让我再问一个问题：“什么数被3除余2？”这两个问题都是很 这里你就必须在23里找所有的奇数，即7，1，5，11，等等。（如果你学过初等集合论，你就是要找交集1223的所有元素。） 而这些所有的数可以写成形如6k1。（k=0，1，2，） 因为6k11（mod 2）,6k12（mod 3）以上的问题写成数学式子就是：“寻找x，使得x1（mod 2），x2（mod 3）。”而答案是：所有形如6k1的数。 这里你就必须在23里找所有的奇数，即7，中国古算书的一个问题 在成书差不多

7、4世纪时的一本中国最古老的数学书之一孙子算经里的下卷第26题，是一个闻名世界的数学问题。这问题有人称它为“孙子问题”现在我们看这问题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”中国古算书的一个问题 在成书差不多4世纪时的一本中国最这问题翻译成现在的白话是：“现在有一些东西不知道它们的个数，三个三个一组剩下2个，五个五个一组剩下3个，七个七个一组剩下2个，问这些东西有多少？” 我们把这个问题再翻译成数学问题，就变成：“寻找x，使得x2（mod 3），x3（mod 5），x2（mod 7）。”这问题翻译成现在的白话是：“现在有一些东西不知道它们的个数， 你只要懂得23

8、，35，27就在里面找那些数同时在这三个集合里就行了。因此由23=，1，2，5，8，11，14，17，20，23，26，29，35=，2，3，8，13，18，23，28，33，38，43，47，27=，5，2，9，16，23，30，37，44，51，58，63，我们很容易看到最小的正整数答案是23。 你只要懂得23，35，27就在里面找那 这和孙子算经的答案：“答曰：二十三”是符合的。 孙子算经还给出解这题的方法： “术曰：三三数之剩二，置一百四十；五五数之剩三，置六十三；七七数之剩二，置三十；并之，得二百三十三，以二百十一减之即得。”而书中接下来就给这一类问题的一般解法： 这和孙子算经的答案

9、：“答曰：二十三”是符合的。 “凡三三数之剩一，则置七十；五五数之剩一，则置二十一；七七数之剩一，则置十五；一百六以上，以一百五减之即得。” 这些解法的叙述，相信许多读者第一次看会觉得莫名其妙，究竟这是在说什么东西？我们现在研究一下。 “凡三三数之剩一，则置七十；五五数之剩一，则置二十孙子算经的解法现在假定“孙子问题”一般的情形：求x使得xr1（mod 3） 0r13xr2（mod 5） 0r25 （I）xr3（mod 7） 0r37由于模3，5，7是两两互素，所以它们的最小公倍数=357335=521 =715105 孙子算经的解法现在假定“孙子问题”一般的情形：求x使得因为 3521（mo

10、d 3）2111（mod 5）1511（mod 7）因此由同余的可乘性我们得于是我们有70r121r215r370r1r1（mod 3）70r1+21r215r321r2r2（mod 5）70r1+21r215r315r3r3（mod 7）因为 3521（mod 3）于是我们有因此同余式组（I）的解是满足下面同余式组的整数值x：x70r121r215r3（mod 3）x70r121r215r3（mod 5） （）x70r121r215r3（mod 7）由于x(70r121r215r3)是3，5，7的倍数，它也会是(3，5，7)的最小公倍数105的倍数。因此同余式组（I）的解是满足下面同余式组的

11、整数值x：x70故（）的解同样是和x70r121r215r3（mod 105）一样。现在回过头看“孙子问题”，r1=2，r2=3，r3=2。由算经的前半段解法是这样：x=702213152210523在古代中国人民有猜岁数，“隔壁算”、“剪管术”、“秦王暗点兵”等数学游戏，就是属于“孙子问题”的范畴和解法。故（）的解同样是和x70r121r215r3（mod 明朝程大位在1583年写的一部后来流传很广的应用数学书直指算法统宗就有一首孙子歌：“三人同行七十稀，五树梅花甘一枝；七子团员正半月，除百零五便得知。”就在诗歌中点明解孙子问题所用到的一些数字。 明朝程大位在1583年写的一部后来流传很广的

12、应用数学中国剩余定理以上的孙子问题解法可以推广为：如果有同余式组：xr1（mod n1）xr2（mod n2）xr3（mod n3）这里0r1n1，0r2n2，0r3u3，而且n1，n2，n3是两两互素，中国剩余定理即GCD（n1，n2）GCD（n1, n3）=GCD（n2，n3）=1。如果能找到整数，满足下面三式：n2n31（mod n1）n1n31（mod n2）n2n11（mod n3）那么xn2n3r1+n1n3r2+rn2n1r3(modn1n2n3)是原同余式组的解。即GCD（n1，n2）GCD（n1, n3）=GCD（n2 迟于中国人，古代的印度数学家也考虑类似“孙子问题”，欧洲

13、在1202年出的意大利数学家斐波那契的算法之书才有两个一次同余问题。而上面的推广，欧洲人要到18世纪才被欧拉重新发现。因此欧洲数学家后来把这定理称为中国剩余定理，而不是“欧拉定理”以纪念中国数学家在这方面的成就。 迟于中国人，古代的印度数学家也考虑类似“孙子问题”例1 找一个最小的正整数被3除余2，被4除余3。解我们现在要解同余式组： x2（mod 3）， x3（mod 4） 先找那些4的倍数被3除余1。从8，12，16，20，我们看到最小的是16。 再找3的倍数被4除余1。从9，12，15，我们试到最小的是9。 即441（mod 3），331（mod 4）例1 找一个最小的正整数被3除余2，被4除余3。例2 让我们回到这篇文章前那个算命先生的玩意儿。算命先生要解x1（mod 2），x1（mod 3），x3（mod 5）。明显的3511（mod 2）2511（mod 3）2311（mod 5）所以由