初等数论孙子定理优质教育课件.ppt

看过《射雕英雄传》的同学应该记得,当年黄蓉身中奇毒,郭靖将她送到瑛姑那里救治,进入瑛姑茅舍,瑛姑就给他们出了一题:“今有物不知其数,三三数之剩二;五五数之剩三:七七数之剩二。问物几何?”黄蓉天资聪慧,她略微思考,答:23。大家是不是很好奇,黄蓉是怎么解出这道题的呢?2020/3/301其实,这就是享誉中外的《中国剩余定理》。剩余问题:在整数除法里,一个数同时除以几个数,整数商后,均有剩余;已知各除数及其对应的余数,从而要求出适合条件的这个被除数的问题,叫做剩余问题。2020/3/302中国剩余定理1247年南宋的数学家秦九韶把《孙子算经》中“物不知其数”一题的方法推广到一般的情况,得到称之为“大衍求一术”的方法,在《数书九章》中发表。这个结论在欧洲要到十八世纪才由数学家高斯和欧拉发现。所以世界公认这个定理是中国人最早发现的,特别称之为“中国剩余定理”(Chineseremaindertheorem)。*阜阳师范学院数科院*古人解法:凡三三数之剩一,则置七十;五五数之剩一,则置二十一;七七数之剩一则置十五;一百六以上,以一百零五减之即得。依定理译成算式解为:70×2+21×3+15×2=233233-105×2=23*阜阳师范学院数科院*明朝数学家程大位在《算法统宗》中把上式总结为一首通俗易懂的歌决:三人同行七十稀,五树梅花廿一枝,七子团圆正半月,除百零五便得知。其中正半月是指15,这个口诀把3,5,7;70,21,15及105这几个关键的数都总结在内了。详细说,歌诀的含义是:用3除的余数乘70,5除的余数乘21,7除的余数乘15,相加后再减去(“除”当“减”讲)105的适当倍数,就是需要求的(最小)解了。2020/3/305列表如下:为什么啊?除数余数最小公倍数衍数乘率各总答数最小答数323×5×7=1055×7235×2×3140+63+30=233233-2×105=23533×7121×1×3723×5115×1×22020/3/306分析:设所求物数为x,则有称之为同余式组。即要求这些同余式的公共解。一般情况下,同余式组可记作:2020/3/307一、一次同余式组的解法——中国剩余定理定理1[孙子定理]m1,m2,,mk是两两互质的正整数,记m=m1m2mk,则(1)的解为其中,整数Mi(1ik),满足MiMi1(modmi).设有同余式组2020/3/308例1解同余式组衍数乘率2020/3/309例2〔韩信点兵〕有兵一队,若列成五行纵队,则末行1人;成六行纵队,则末行5人;成七行纵队,则末行4人;成十一行纵队,则末行10人。求兵数。——余数——衍数2020/3/3010