中国剩余定理.pptx

单击此处编辑母版标题样式,编辑母版文本样式,第二级,第三级,第四级,第五级,中国剩余定理,名题赏析,北师大,2003,课标版选修,3-1,江西省上饶市德兴市花桥中学 俞晓妹,看过,射雕英雄传,的同学应该记得，当年黄蓉身中奇毒，郭靖将她送到南帝那里救治，误入瑛姑茅舍，瑛姑给他们出了一些题，,黄蓉天资聪慧，都一一答上,，临走她给瑛姑出了一题：,“有一个数，除五剩二，除四剩三，除三刚刚好，问这个数是多少？”,情景导入,韩信点兵,韩信点兵,韩信点兵,每3人一列，余,1,人,每,5,人一列，余,1,人,每,7,人一列，余,1,人,问韩信有多少兵？,孙子算经,中的物不知数,今有物不知其数,三三数之剩二，,五五数之剩三，,七七数之剩二，,问物几何？,孙子算经,“,物不知数,”,问题用现代数学语言表示，就是求一次同余式组的解的问题，即：,列举筛选法,（1）2，5，8，11，14，17，20，,23,，,26,29,.,（用3除余2 ）,（2）3，8，13，18，,23,，28，.,（用5除余 3）,（3）2，9，16，,23,，30，.,（用7除余2）,所以最小的一个数是23,递推法,我们先考虑其中一个条件,为使搜寻更迅速,应该先考虑除数最大的那个条件即“7 除余,2,”，可选择,9,作为起点，由于,9,不符合另两个条件，再加上,7,的倍数，因,16,不满足，再加,7,得,23,，正好满足剩余两个条件。即,23.,以上的思考过程，我们以下面的形式进行表达,称之为,“,递推流程图,”,答:符合题意的最小正整数为,23,。,小试牛刀,有一个数，二数余一，五数余二，七数余三，九数余四，问本数？（选自南宋数学家杨辉,1275,年写成的续古摘奇算法）,答:符合题意的最小正整数为 157。,余数,2 3 2,70,21,15,计算,70*2+21*3+15*2-105*2=23,？,.,1,.,1,？,.,？,1,除数,3,5,7,单因子构件凑成法,孙子算经中给出的算法,：,三三数之剩二置一百四十，五五数之,剩三置,六十三，七七,数之剩二置,三十，并之得二百三十三，以二百十减之，即得.,明朝数学家程大位在算法统宗中把上,式总结为一首通俗易懂的歌诀：,三,人同行七十稀，五树梅花廿一,枝，,七子团圆正半月，除百零五便得知.,中国剩余定理,方法应用,一个数，五五数之余三，七七数之剩,一，九九数之剩二，问这个数是多少,?,方法一,：,方法二,余数,3 1 2,126,225,280,计算,126*3+225*1+280*2-315*3=218,？,.,1,.,1,？,.,？,1,除数,5,7,9,为什么叫中国剩余定理,1247,年南宋的数学家秦九韶把,孙子算经,中,“,物不知其数,”,一题的方法推广到一般的情况，称之为,“,大衍求一术,”,的方法，在,数书九章,中发表。这个结论在欧洲要到,1801,年才由数学家高斯在算术探究中发现。公元1852年,英国基督教士伟烈亚力将孙子算经,数书九章(1247),中的“物不知其数”问题的解法传到欧洲。公元187,6,年,马蒂生指出:秦九韶的解法完全符合高斯的定理。而此时,高斯定理已比秦九韶的大衍求一术晚五百多年.所以世界公认这个定理是中国人最早发现的，特别称之为,“,中国剩余定理,”。,应用,中国剩余定理的一个应用是制定古代历法.实际上,从汉末到宋末1000余年的时间中,有很多天文学家熟悉一次同余式的解法,他们在编制历法时利用它来推算“上元积年”.,应用,中国剩余定理虽是数论中的基本定理,但是在计算机密码学中有着重要的应用.例如在Rabin密码算法中用于解密运算.在RSA密码算法中,中国剩余定理同样可用于RSA的解密运算,而且使RSA的机密速度大约提高4倍左右,这无论对于软件还是硬件实现RSA密码算法都是非常重要的.,小结,孙子问题的解法,定理应用,中国剩余定理,作业布置,1.收集和整理中国古代数学成就，体会中国数学家为世界数学发展所作出的巨大贡献。,2,黄,蓉原题：一个数，除以六余一，除以五余二，除以四余三，除以三刚刚好，问这个数是多少？,THANK YOU,