1、中國剩余定理中國剩余定理2015.08.22整數除法v被除數被除數除數除數=商余數（余數除數）商余數（余數除數）A B = C Rv（被除數余數）除數（被除數余數）除數 = 商商v(A R) B = C例1、 一個兩位數,用它除58余2,除73余3,除85余1,求這個兩位數v用它除58余2，意外著這個兩位數是56（58 2）的因數。同樣的也是70和84的因數。v所以這個兩位數是56，70，84的公因數，答案是14 。例2、有一盒乒乓球，每次8個8個地數，10個10個地數，12個12個地數，最后總是剩下3個.這盒乒乓球至少有多少個?v因為每次都多出3個，所以拿走3個乒乓球，那么不論是8個8個地數

2、, 10個10個地數, 12個12個地數，都沒有剩余，這時乒乓球的個數就應該是8、10和12的公倍數。8，10，12=120 。v120+3=123v 所以這盒乒乓球至少有123個。例3、把幾十個蘋果平均分成若干份,每份4個余2個,每份10個余8個,每份25個余23個.這堆蘋果共有幾個？v題目的意思相當于：這個數除以4缺2，除以10缺2，除以25也缺2。v因此加上2后，除以4、除以10和除以25時，就都正好能整除了，也就是4，10和25的公倍數。v4，10，25=100，100一2=98，所以這堆蘋果的數量是98。例4、 有一個數，除以8余數是3，除以11余數是2，這個數最小是多少？v由于這個

3、數除以8和11的余數不相同，而且缺少的 數也不相同，因此不能直接利用最小公倍數來解決 v我們先看“除以11余2這個條件，從小到大依次在所有滿足“除以11余2”的數中尋找“除以8余3”的數。v 2+11=13，138=15，不符合；v 13+11=24，248=3，也不符合；v 24+11=35，358=43，符合條件。v 因此這個數最小是35 例5、一堆糖果，4個一數多1個，9個一數多4個，11個一數多9個。這堆糖果至少有多少個?v這個問題可以概括為：一個數，除以4余1，除以9余4，除以11余9。v我們可以從滿足“除以11余9”的數中，找出“除以9余4”的數，這只要依次加上11即可；然后再找出

4、“除以4余1”的數，這需要依次加上9和11的最小公倍數99即可。v9+11=20 209=22，不符合“除以9余4的條件；v20+11=31 319=34，符合“除以9余4”的條件；v 但314 =73，不符合“除以4余1的條件；v31+99=130，1304=322，也不符合“除以4余1”的條件；v130+99 =229，2294 =571 符合“除以4余1”的條件。v 因此這堆糖果至少有229個。 “韓信點兵韓信點兵”的故事的故事韓信閱兵時，讓一隊士兵韓信閱兵時，讓一隊士兵5人一行排隊從他面前走人一行排隊從他面前走過，他記下最后一行士兵的人數（過，他記下最后一行士兵的人數（1人）；再讓這人

5、）；再讓這隊士兵隊士兵6人一行排隊從他面前走過，他記下最后一人一行排隊從他面前走過，他記下最后一行士兵的人數（行士兵的人數（5人）；再讓這隊士兵人）；再讓這隊士兵7人一行排人一行排隊從他面前走過，他記下最后一行士兵的人數（隊從他面前走過，他記下最后一行士兵的人數（4人），再讓這隊士兵人），再讓這隊士兵11人一行排隊從他面前走過，人一行排隊從他面前走過，他記下最后一行士兵的人數（他記下最后一行士兵的人數（10人）。人）。然后韓信就憑這些數，可以求得這隊士兵的總人數然后韓信就憑這些數，可以求得這隊士兵的總人數(2111,4421,)。 孫子算經孫子算經中的題目中的題目 我國古代數學名著我國古代數學

6、名著孫子算經孫子算經中有中有“物不知數物不知數”的題目：的題目： 今有物不知其數，今有物不知其數， 三三數之剩二，三三數之剩二， 五五數之剩三，五五數之剩三， 七七數之剩二，七七數之剩二， 問物幾何？問物幾何？v還有專門用來解決同一個數除以還有專門用來解決同一個數除以3，5和和7的問題的歌訣的問題的歌訣 ：“三人同行七十稀，五樹梅花廿一枝，七子團圓正半月，三人同行七十稀，五樹梅花廿一枝，七子團圓正半月，除百零五便得知除百零五便得知”v實際上實際上70是能被是能被5和和7整除但被整除但被3除余除余1，21能被能被3和和7整整除但除但5除余除余1，15能被能被3和和5整除但被整除但被7除余除余1。

7、這個系統算。這個系統算法是南宋時期的數學家秦九韶研究后得到的。法是南宋時期的數學家秦九韶研究后得到的。 這就是著這就是著名的中國剩余定理。名的中國剩余定理。例6、今有物不知其數， 三三數之剩二， 五五數之剩三， 七七數之剩二， 問物幾何？v題目中此數被題目中此數被3除余除余2，那就用，那就用70乘以乘以2，被，被5除余除余3。v歌訣歌訣 ：“三人同行七十稀，五樹梅花廿一枝，三人同行七十稀，五樹梅花廿一枝，七子團圓正半月，除百零五便得知七子團圓正半月，除百零五便得知”v那么就用那么就用21乘乘3，被，被7除余除余2，那就，那就15乘乘2，相，相加：加：v702 + 213 +152=233。 v

8、看情況減看情況減3、5、7的最小公倍數的倍數。此題的最小公倍數的倍數。此題減減105的的2倍，得到倍，得到23。例7、一個數，除以5余1，除以7余2，除以9余4。這個數最小是多少? v這道題目同樣可以用例5的方法進行計算，但是現在我們準備采用類似于例6的方法。例6的方法之所以方便，是因為歌訣中給出了70，21和15這三個數，那么這道題目中又該是多少呢?v歌訣中的70正好是能被5和7整除，而被3除余1的最小數；21正好是能被3和7整除，而被5除余1的最小數；15正好是能被3和5整除，而被7除余1的最小數。v利用這個思路，我們來解答例7。v 因為7，9 =63，635=123；而63 x 2=126，1265=251。v所以能被7和9整除，而被5除余1的最小數是126。例7 (續) 、一個數，除以5余1，除以7余2，除以9余4。這個數最小是多少? v能被7和9整除，而被5除余1的最小數是126。v同樣的方法，我們可以找出能被5和9整除，而被7除余1的最小數是225；能被5和7整除，而被9除余1的最小數是280。v 1126+2x225+4280=696