§《射雕英雄传》的同学应该记得,当年黄蓉身中奇毒,郭靖将她送到瑛姑那里救治,进入瑛姑茅舍,瑛姑就给他们出了一题:“今有物不知其数,三三数之剩二;五五数之剩三:七七数之剩二。问物几何?”黄蓉天资聪慧,她略微思考,答:23。大家是不是很好奇,黄蓉是怎么解出这道题的呢?,这就是享誉中外的《中国剩余定理》。剩余问题:在整数除法里,一个数同时除以几个数,整数商后,均有剩余;已知各除数及其对应的余数,从而要求出适合条件的这个被除数的问题,叫做剩余问题。《孙子算经》中“物不知其数”一题的方法推广到一般的情况,得到称之为“大衍求一术”的方法,在《数书九章》中发表。这个结论在欧洲要到十八世纪才由数学家高斯和欧拉发现。所以世界公认这个定理是中国人最早发现的,特别称之为“中国剩余定理”(Chineseremaindertheorem)。:凡三三数之剩一,则置七十;五五数之剩一,则置二十一;七七数之剩一则置十五;一百六以上,以一百零五减之即得。依定理译成算式解为:70×2+21×3+15×2=233233-105×2=《算法统宗》中把上式总结为一首通俗易懂的歌决:三人同行七十稀,五树梅花廿一枝,七子团圆正半月,除百零五便得知。其中正半月是指15,这个口诀把3,5,7;70,21,15及105这几个关键的数都总结在内了。详细说,歌诀的含义是:用3除的余数乘70,5除的余数乘21,7除的余数乘15,相加后再减去(“除”当“减”讲)105的适当倍数,就是需要求的(最小)解了。:为什么啊?除数余数最小公倍数衍数乘率各总答数最小答数323×5×7=1055×7235×2×3140+63+30=233233-2×105=23533×7121×1×3723×5115×1×:设所求物数为x,则有称之为同余式组。即要求这些同余式的公共解。一般情况下,同余式组可记作:、一次同余式组的解法——中国剩余定理定理1[孙子定理]m1,m2,,mk是两两互质的正整数,记m=m1m2mk,则(1)的解为其中,整数Mi(1ik),满足MiMi1(modmi)./5/5
初等数论§4.2孙子定理ppt课件 来自淘豆网www.taodocs.com转载请标明出处.