中国剩余定理.ppt

《中国剩余定理.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、5.中国剩余定理公元前后的《孙子算经》中有“物不知数”问题：“今有物不知其数，三三数之余二，五五数之余三，七七数之余二，问物几何？”答为“23”。也就是求同余式组x≡2（mod3），x≡3（mod5），x≡2（mod7）（式中a≡b（modm）表示m整除a－b）的正整数解。明朝程大位用歌谣给出了该题的解法：“三人同行七十稀，五树梅花廿一枝，七子团圆月正半，除百零五便得知。”即解为x≡2×70＋3×21＋2×15≡233≡23(mod105）三三数之剩二，则置一百四十；五五数之剩三，置六十三；七七数之剩二，置三十；并之得

2、二百三十三，以二百一十减之，即得。凡三三数之剩一，则置七十；五五数之剩一，则置二十一；七七数之剩一，则置十五，一百六以上，以一百五减之，即得除数余数最小公倍数衍数乘率各总答数最小答数323*5*7=1055*7235*2*2140+63+30=233233-2*105=23537*3121*1*3723*5115*1*2例有一个年级的同学，每9人一排多6人，每7人一排多2人，每5人一排多3人，问这个年级至少有多少人？题中9、7、5三个数两两互质。则〔7，5〕=35；〔9，5〕=45；〔9，7〕=63；〔9，7，5〕=3

3、15为了使35被9除余1，用35×8=280；使45被7除余1，用45×5=225；使63被5除余1，用63×2=126。然后，280×6＋225×2＋126×3=2508，因为，2508>315，所以，2508－315×7=303，就是所求的数。求解如下形式的同余方程组其中：，，，。令r个整数两两互素，是任意r个整数，则r个同余方程组（其中）模有惟一解，且该解的表达式为：其中，，,。中国剩余定理的用途之一是：给出了一种方法，使非常大的数对M的模运算转化到更小的数上来进行运算，当M为150位或150位以上的时候，这种方

4、法非常有效。除数余数最小公倍数衍数乘率各总答数m1b1m=m1m2…mkM1M’1M1M’1b1m2b2M2M’2M2M’2b2……………mkbkMkM’kMkM’kbk例解同余方程组解此时m=5*6*7*11=2310M1=6*7*11=462，M2=5*7*11=385M3=5*6*11=330，M4=5*6*7=210因为M’iMi≡1(modmi),i=1,2,3,4得到M’1=3,M’2=1,M’3=1,M’4=1故x≡3*462*b1+385b2+330b3+210b4(mod2310)例韩信点兵：有兵一对

5、，若列成五行纵队，则末行一人，成六行纵队，则末行五人，成七行纵队，则末行四人，成十一行纵队，则末行10人，求兵数。解：此时b1=1,b2=5,b3=4,b4=10由上例即得x≡3*462+385*5+330*4+210*10≡6731≡2111(mod2310)