《初等数论§4.2孙子定理》由会员分享，可在线阅读，更多相关《初等数论§4.2孙子定理（13页珍藏版）》请在金锄头文库上搜索。
1、2019/5/21,1,4.2 孙子定理,李 新 年,2019/5/21,2,看过射雕英雄传的同学应该记得，当年黄蓉身中奇毒，郭靖将她送到瑛姑那里救治，进入瑛姑茅舍，瑛姑就给他们出了一题： “今有物不知其数，三三数之剩二；五五数之剩三：七七数之剩二。问物几何？” 黄蓉天资聪慧，她略微思考，答：23。 大家是不是很好奇，黄蓉是怎么解出这道题的呢？,2019/5/21,3,其实，这就是享誉中外的中国剩余定理。,剩余问题:在整数除法里，一个数同时除以几个数，整数商后，均有剩余；已知各除数及其对应的余数，从而要求出适合条件的这个被除数的问题，叫做剩余问题。,中国剩余定理,1247年南宋的数学家秦九韶把
2、孙子算经中“物不知其数”一题的方法推广到一般的情况，得到称之为“大衍求一术”的方法，在数书九章中发表。这个结论在欧洲要到十八世纪才由数学家高斯和欧拉发现。所以世界公认这个定理是中国人最早发现的，特别称之为“中国剩余定理” （Chinese remainder theorem）。,2019/5/21,阜阳师范学院 数科院,4,古人解法：,凡三三数之剩一，则置七十；五五数之剩一，则置二十一；七七数之剩一则置十五；一百六以上，以一百零五减之即得。 依定理译成算式解为： 702213152233 233105223,2019/5/21,阜阳师范学院 数科院,5,2019/5/21,6,明朝数学家程大位
3、在算法统宗中把上式总结为一首通俗易懂的歌决： 三人同行七十稀，五树梅花廿一枝， 七子团圆正半月，除百零五便得知。 其中正半月是指15，这个口诀把3，5，7；70，21，15及105这几个关键的数都总结在内了。详细说，歌诀的含义是：用3除的余数乘70，5除的余数乘21，7除的余数乘15，相加后再减去（“除”当“减”讲）105的适当倍数，就是需要求的（最小）解了。,2019/5/21,7,列表如下：,为什么啊？,2019/5/21,8,分析：设所求物数为x，则有,称之为同余式组。,即要求这些同余式的公共解。,一般情况下，同余式组可记作：,2019/5/21,9,一、一次同余式组的解法中国剩余定理,
4、定理1孙子定理,m1, m2, , mk是两两互质的正整数，,记 m = m1m2mk ，,则(1)的解为,其中，整数Mi（1 i k），满足MiMi 1 (mod mi).,设有同余式组,2019/5/21,10,例1 解同余式组,衍数,乘率,2019/5/21,11,例2 韩信点兵有兵一队，若列成五行纵队，则 末行1人；成六行纵队，则末行5人；成七行纵队， 则末行4人；成十一行纵队，则末行10人。求兵数。,余数,衍数,2019/5/21,12,列表如下：,其它略,14623,53851,43301,102101,6731,3,1,1,1,2019/5/21,新疆师范高等专科学校 数学学院,13,敬请指导，谢谢！,
