5.中国剩余定理中国剩余定理 v公元前后的公元前后的《《孙子算经孙子算经》》中有中有“物不知数物不知数”问题：问题：“今有物今有物不知其数，三三数之余二不知其数，三三数之余二 ，五五数之余三，五五数之余三 ，七七数之余二，，七七数之余二，问物几何？问物几何？”答为答为“23”也就是求同余式组也就是求同余式组x≡2 （（mod3），），x≡3 （（mod5 ），），x≡2 （（mod7）（式中）（式中a≡b （（modm）表示）表示m整除整除a－－b ）的正整数解的正整数解v明朝程大位用歌谣给出了该题的解法：明朝程大位用歌谣给出了该题的解法：“三人同行七十稀，三人同行七十稀，五树梅花廿一枝，七子团圆月正半，除百零五便得知五树梅花廿一枝，七子团圆月正半，除百零五便得知 ” 即解为即解为 x≡2×70＋＋3×21＋＋2×15≡233≡23(mod105）） v三三数之剩二，则置一百四十；五五数之剩三，置六十三；三三数之剩二，则置一百四十；五五数之剩三，置六十三；七七数之剩二，置三十；并之得二百三十三，以二百一十减七七数之剩二，置三十；并之得二百三十三，以二百一十减之，即得凡三三数之剩一，则置七十；五五数之剩一，则之，即得。
凡三三数之剩一，则置七十；五五数之剩一，则置二十一；七七数之剩一，则置十五，一百六以上，以一百置二十一；七七数之剩一，则置十五，一百六以上，以一百五减之，即得五减之，即得 除数除数 余数余数最小公倍数最小公倍数衍数衍数 乘率乘率各总各总答数答数最小最小答数答数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〕〕=315 为了使为了使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，就是所求的数就是所求的数 v求解如下形式的同余方程组求解如下形式的同余方程组 其中：其中： ，， ，， ，， v令令r个整数个整数 两两互素，两两互素， 是任意是任意r个整数，个整数，则则r个同余方程组个同余方程组 （其中（其中 ）） 模模 有惟一解，且该解的表达式为：有惟一解，且该解的表达式为： 其中，其中， ，， , 。
v中国剩余定理的用途之一是：给出了一种方法，中国剩余定理的用途之一是：给出了一种方法，使非常大的使非常大的数对数对M的模运算转化到更小的数上来进行运算的模运算转化到更小的数上来进行运算，当，当M为为150位位或或150位以上的时候，这种方法非常有效位以上的时候，这种方法非常有效 除除数数余余数数最小公最小公倍数倍数衍数衍数乘率乘率各总各总答数答数m1b1m=m1m2…mkM1M’1M1M’1b1m2b2M2M’2M2M’2b2……………mkbkMkM’kMkM’kbk v例例 解同余方程组解同余方程组v解解 此时此时m=5*6*7*11=2310 M1=6*7*11=462，， M2=5*7*11=385 M3=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) v例例 韩信点兵韩信点兵：有兵一对，若列成五行纵队，则末行一人，：有兵一对，若列成五行纵队，则末行一人，成六行纵队，则末行五人，成七行纵队，则末行四人，成十成六行纵队，则末行五人，成七行纵队，则末行四人，成十一行纵队，则末行一行纵队，则末行10人，求兵数。
人，求兵数v解：此时解：此时b1=1, b2=5, b3=4, b4=10由上例即得由上例即得x≡3*462+385*5+330*4+210*10 ≡6731 ≡2111(mod 2310) 谢谢观赏！谢谢观赏！ 。