中國(guó)剩余定理

1、中國(guó)剩余定理在中國(guó)古代勞動(dòng)人民中，長(zhǎng)期流傳著“隔墻算”、“剪管術(shù)”、“秦王暗點(diǎn)兵”等數(shù)學(xué)游戲。有一首“孫子歌”，甚至遠(yuǎn)渡重洋，輸入日本：“三人同行七十稀，五樹(shù)梅花廿一枝，七子團(tuán)圓正半月，除百零五便得知。”這些饒有趣味的數(shù)學(xué)游戲，以各種不同形式，介紹世界聞名的“孫子問(wèn)題”的解法，通俗地反映了中國(guó)古代數(shù)學(xué)一項(xiàng)卓越的成就?！皩O子問(wèn)題”在現(xiàn)代數(shù)論中是一個(gè)一次同余問(wèn)題，它最早出現(xiàn)在中國(guó)公元四世紀(jì)的數(shù)學(xué)著作孫子算經(jīng)中。孫子算經(jīng)卷下“物不知數(shù)”題說(shuō)：有物不知其數(shù)，三個(gè)一數(shù)余二，五個(gè)一數(shù)余三，七個(gè)一數(shù)又余二，問(wèn)該物總數(shù)幾何？顯然，這相當(dāng)于求不定方程組N=3x+2,N=5y+3,N=7z+2的正整數(shù)解N，或用現(xiàn)

2、代數(shù)論符號(hào)表示，等價(jià)干解下列的一次同余組。孫子算經(jīng)所給答案是N=23。由于孫子問(wèn)題數(shù)據(jù)比較簡(jiǎn)單，這個(gè)答數(shù)通過(guò)試算也可以得到。但是孫子算經(jīng)并不是這樣做的。“物不知數(shù)”題的術(shù)文指出解題的方法多三三數(shù)之，取數(shù)七十，與余數(shù)二相乘；五五數(shù)之，取數(shù)二十一，與余數(shù)三相乘；七七數(shù)之，取數(shù)十五，與余數(shù)二相乘。將諸乘積相加，然后減去一百零五的倍數(shù)。列成算式就是：N=702+213+1522105。這里105是模數(shù)3、5、7的最小公倍數(shù)，容易看出，孫子算經(jīng)給出的是符合條件的最小正整數(shù)。對(duì)于一般余數(shù)的情形，孫子算經(jīng)術(shù)文指出，只要把上述算法中的余數(shù)2、3、2分別換成新的余數(shù)就行了。以R1、R2、R3表示這些余數(shù)，那么孫

3、子算經(jīng)相當(dāng)于給出公式N=70R1+21R2+15R3P105（p是整數(shù)）。孫子算法的關(guān)鍵，在于70、21和15這三個(gè)數(shù)的確定。后來(lái)流傳的孫子歌中所說(shuō)“七十稀”、“廿一枝”和“正半月”，就是暗指這三個(gè)關(guān)鍵的數(shù)字。孫子算經(jīng)沒(méi)有說(shuō)明這三個(gè)數(shù)的來(lái)歷。實(shí)際上，它們具有如下特性：也就是說(shuō)，這三個(gè)數(shù)可以從最小公倍數(shù)M=357=105中各約去模數(shù)3、5、7后，再分別乘以整數(shù)2、1、1而得到。假令k1=2，K2=1，K3=1，那么整數(shù)Ki（i=1，2，3)的選取使所得到的三數(shù)70、21、15被相應(yīng)模數(shù)相除的時(shí)候余數(shù)都是1。由此出發(fā)，立即可以推出，在余數(shù)是R1、R2、R3的情況下的情況。解法中的三個(gè)關(guān)鍵數(shù)70，2

4、1，15，有何妙用，有何性質(zhì)呢?首先70是3除余1而5與7都除得盡的數(shù)，所以70a是3除余a，而5與7都除得盡的數(shù)，21是5除余1，而3與7都除得盡的數(shù)，所以21b是5除余b，而3與7除得盡的數(shù)。同理，15c是7除余c，3與5除得盡的數(shù)，總加起來(lái) 70a+21b+15c 是3除余a，5除余b ，7除余c的數(shù)，也就是可能答案之一，但可能不是最小的，這數(shù)加減105(105=357)仍有這樣性質(zhì)，可以多次減去105而得到最小的正數(shù)解。附：如70，其實(shí)是要找余2的，但只要找到了余1的再乘2即余二了。孫子問(wèn)題的解法，以現(xiàn)代的說(shuō)法，是找出三個(gè)關(guān)鍵數(shù)70，21，15。解法的意思就是用70乘3除所得的余數(shù)，2

5、1乘5除所得的余數(shù)，15乘7除所得的余數(shù)，然后總加起來(lái)，除以105的余數(shù)就是答案。即題目的答案為 702+213+152=140+63+30=233233-2105=23公式：70a+21b+15c-105n題中有三個(gè)數(shù)，分別為3、5、7，573余數(shù)為2，取35；375余數(shù)為1，要使余數(shù)為3，只需將37擴(kuò)大3倍變成63即可；同樣357的余數(shù)為1，要使余數(shù)為2，則將35擴(kuò)大2倍，變成30。中國(guó)剩余定理”算理及其應(yīng)用：為什么這樣解呢？因?yàn)?0是5和7的公倍數(shù)，且除以3余1。21是3和7的公倍數(shù)，且除以5余1。15是3和5的公倍數(shù)，且除以7余1。（任何一個(gè)一次同余式組，只要根據(jù)這個(gè)規(guī)律求出那幾個(gè)關(guān)鍵

6、數(shù)字，那么這個(gè)一次同余式組就不難解出了。）把70、21、15這三個(gè)數(shù)分別乘以它們的余數(shù)，再把三個(gè)積加起來(lái)是233，符合題意，但不是最小，而105又是3、5、7的最小公倍數(shù)，去掉105的倍數(shù)，剩下的差就是最小的一個(gè)答案。用歌訣解題容易記憶，但有它的局限性，只能限于用3、5、7三個(gè)數(shù)去除，用其它的數(shù)去除就不行了。后來(lái)中國(guó)數(shù)學(xué)家又研究了這個(gè)問(wèn)題，運(yùn)用了像上面分析的方法那樣進(jìn)行解答。例1：一個(gè)數(shù)被3除余1，被4除余2，被5除余4，這個(gè)數(shù)最小是幾？題中3、4、5三個(gè)數(shù)兩兩互質(zhì)。則4，5=20；3，5=15；3，4=12；3，4，5=60。為了使20被3除余1，用202=40；使15被4除余1，用153=

7、45；使12被5除余1，用123=36。然后，401+452+364=274，因?yàn)椋?7460，所以，274604=34，就是所求的數(shù)。例2：一個(gè)數(shù)被3除余2，被7除余4，被8除余5，這個(gè)數(shù)最小是幾？題中3、7、8三個(gè)數(shù)兩兩互質(zhì)。則7，8=56；3，8=24；3，7=21；3，7，8=168。為了使56被3除余1，用562=112；使24被7除余1，用245=120。使21被8除余1，用215=105；然后，1122+1204+1055=1229，因?yàn)椋?229168，所以，12291687=53，就是所求的數(shù)。例3：一個(gè)數(shù)除以5余4，除以8余3，除以11余2，求滿足條件的最小的自然數(shù)。題中5

8、、8、11三個(gè)數(shù)兩兩互質(zhì)。則8，11=88；5，11=55；5，8=40；5，8，11=440。為了使88被5除余1，用882=176；使55被8除余1，用557=385；使40被11除余1，用408=320。然后，1764+3853+3202=2499，因?yàn)椋?499440，所以，24994405=299，就是所求的數(shù)。例4：有一個(gè)年級(jí)的同學(xué)，每9人一排多5人，每7人一排多1人，每5人一排多2人，問(wèn)這個(gè)年級(jí)至少有多少人 ？（幸福123老師問(wèn)的題目）題中9、7、5三個(gè)數(shù)兩兩互質(zhì)。則7，5=35；9，5=45；9，7=63；9，7，5=315。為了使35被9除余1，用358=280；使45被7除

9、余1，用455=225；使63被5除余1，用632=126。然后，2805+2251+1262=1877，因?yàn)椋?877315，所以，18773155=302，就是所求的數(shù)。例5：有一個(gè)年級(jí)的同學(xué)，每9人一排多6人，每7人一排多2人，每5人一排多3人，問(wèn)這個(gè)年級(jí)至少有多少人 ？ 題中9、7、5三個(gè)數(shù)兩兩互質(zhì)。則7，5=35；9，5=45；9，7=63；9，7，5=315。為了使35被9除余1，用358=280；使45被7除余1，用455=225；使63被5除余1，用632=126。然后，2806+2252+1263=2508，因?yàn)椋?508315，所以，25083157=303，就是所求的數(shù)。

10、（例5與例4的除數(shù)相同，那么各個(gè)余數(shù)要乘的“數(shù)”也分別相同，所不同的就是最后兩步。）關(guān)于“中國(guó)剩余定理”類型題目的另外解法“中國(guó)剩余定理”解的題目其實(shí)就是“余數(shù)問(wèn)題”，這種題目，也可以用倍數(shù)和余數(shù)的方法解決。不懂論壇上有沒(méi)人發(fā)過(guò)。小學(xué)奧賽考試時(shí)學(xué)習(xí)過(guò)，也用過(guò)，現(xiàn)在把方法寫(xiě)出來(lái)，如果懂的也別笑我，呵呵。例一，一個(gè)數(shù)被5除余2，被6除少2，被7除少3，這個(gè)數(shù)最小是多少？解法：題目可以看成，被5除余2，被6除余4，被7除余4。看到那個(gè)“被6除余4，被7除余4”了么，有同余數(shù)的話，只要求出6和7的最小公倍數(shù)，再加上4，就是滿足后面條件的數(shù)了，6X7+4=46。下面一步試下46能不能滿足第一個(gè)條件“一個(gè)

11、數(shù)被5除余2”。不行的話，只要再46加上6和7的最小公倍數(shù)42，一直加到能滿足“一個(gè)數(shù)被5除余2”。這步的原因是，42是6和7的最小公倍數(shù)，再怎么加都會(huì)滿足“被6除余4，被7除余4”的條件。46+42=8846+42+42=13046+42+42+42=172這是一種形式的，它的前提是條件中出現(xiàn)同余數(shù)的情況，如果遇到?jīng)]有的，下面講例二，一個(gè)班學(xué)生分組做游戲，如果每組三人就多兩人，每組五人就多三人，每組七人就多四人，問(wèn)這個(gè)班有多少學(xué)生？解法：題目可以看成，除3余2，除5余3，除7余4。沒(méi)有同余的情況，用的方法是“逐步約束法”，就是從“除7余4的數(shù)”中找出符合“除5余3的數(shù)”，就是再7上一直加4，

12、直到所得的數(shù)除5余3。得出數(shù)為18，下面只要在18上一直加7和5得最小公倍數(shù)35，直到滿足“除3余2”4+7=1111+7=1818+35=53這種方法也可以解“中國(guó)剩余定理”解的題目。比“中國(guó)剩余定理”更好理解，我覺(jué)的速度上會(huì)比那個(gè)繁瑣的公式化的解題更快。大家可以試下. 所以：一共有5個(gè) 187 367 547 727 907此題的初等解法四川省三臺(tái)縣工商局王志成的初等解法，簡(jiǎn)單、方便、可以永遠(yuǎn)的延續(xù)下去。條件1、三三數(shù)之余二 ，條件2、五五數(shù)之余三 ，條件3、七七數(shù)之余二，條件4、十一十一數(shù)之余七，條件5、十三十三數(shù)之余五，條件6、十七十七數(shù)之余七，滿足條件1為等差數(shù)列：3N+2。將等差列

13、3N+2取5項(xiàng)有：2，5，8，11，14，必然有一項(xiàng)滿足條件2，五五數(shù)之余三，結(jié)果為8，同時(shí)滿足條件1和2的為等差數(shù)列：15N+8。將等差列15N+8取7項(xiàng)有：8，23，38，53，68，83，98，必然有一項(xiàng)滿足條件3，七七數(shù)之余二，結(jié)果為23，同時(shí)滿足條件1，2，3的為等差數(shù)列：23+ 105N。將等差列23+ 105N取11項(xiàng)有：23，128，233，338，443，548，653，758，863，968，1073，必然有一項(xiàng)滿足條件4，十一十一數(shù)之余七，結(jié)果為128，同時(shí)滿足條件1，2，3，4的為等差數(shù)列：128+1155N。將等差列128+1155N取13項(xiàng)有：128，1283，24

14、38，3593，4748，5903，7058，8213，9368，10523，11678，12833，13988，必然有一項(xiàng)滿足條件5，十三十三數(shù)之余五，結(jié)果為3593，同時(shí)滿足條件1，2，3，4，5的為等差數(shù)列：3593+15015N。將等差列3593+15015N N取17項(xiàng)有：3593，18608，33623，48638，63653，78668，93683，108698，123713，138728，153743，168758，183773，198788，213803，228818，243833，必然有一項(xiàng)滿足條件6，十七十七數(shù)之余七，結(jié)果為198788，同時(shí)滿足條件1，2，3，4，5，6

15、的為等差數(shù)列：198788+255255N。數(shù)列化簡(jiǎn)當(dāng)?shù)炔顢?shù)列的首項(xiàng)及公差較大時(shí)，對(duì)于求任何素因子的余數(shù)，都可以先進(jìn)行化簡(jiǎn)計(jì)算。如在該問(wèn)題的基礎(chǔ)上,增加十九十九數(shù)余5，如果對(duì)198788+255255N取19項(xiàng)再尋找每一項(xiàng)的余數(shù)，用筆算是相當(dāng)?shù)牟环奖?，我們用首?xiàng)和公差分別除以19的余數(shù)，得新的等差數(shù)列：10+9N，取19項(xiàng)之內(nèi)有：10，0(當(dāng)滿或超過(guò)19時(shí)減去19再算)，9，18，8，17，7，16，6，15，5，當(dāng)出現(xiàn)與余數(shù)相同的數(shù)后,就可以不再計(jì)算了。因該數(shù)列第11項(xiàng)除以19余5。即原數(shù)列的第11項(xiàng)除以19必然余5，198788+255255*（11-1）=2751338，得等差數(shù)列275

16、1338+4849845N的數(shù),為滿足上面七個(gè)條件的數(shù)。如何判別錯(cuò)題？在計(jì)算余數(shù)問(wèn)題上，很容易出現(xiàn)錯(cuò)題，正確的題有解，錯(cuò)誤的題是無(wú)解的。什么是錯(cuò)題？題意自相矛盾的題是錯(cuò)題。判斷標(biāo)準(zhǔn)：一個(gè)數(shù)除以一個(gè)素因子只有一個(gè)余數(shù)；除以合數(shù)時(shí)，要看它與合數(shù)的素因子的余數(shù)是否有矛盾。素因子的重復(fù)。即M/A余C，式中的M與A都是固定的，那么，余數(shù)C只能有一個(gè)。除以同一個(gè)素因子可以在題中出現(xiàn)多次，但余數(shù)必須相同，否則，就是錯(cuò)題。如，除以3余1，除以5余2，除以7余3，除以3余2，問(wèn)該數(shù)為多少？這里的除以3余1與除以3余2自相矛盾，為錯(cuò)題。單個(gè)素因子組成的合數(shù)。如，除以3余1，除以5余2，除以7余3，除以9余8，問(wèn)該

17、數(shù)為多少？因?yàn)椋?是由素因子3組成的，既然前面明示除以3余1，那么，這里的除以9必須服從該條件。因8/3余2與除以3余1矛盾，該題為錯(cuò)題。滿足除以3余1的在9之內(nèi)只有1+3N為：除9余1，余4，余7。除以9余2，3，5，6，8，0都屬于錯(cuò)題。多個(gè)素因子組成的合數(shù)。如，除以3余1，除以5余2，除以7余3，除以15余8，問(wèn)該數(shù)為多少？因?yàn)?，這里的除以15余8，8/3余2與前面的除以3余1矛盾，8/5余3與前面的除以5余2矛盾，該題為錯(cuò)題。同時(shí)滿足除以3余1，除以5余2有：7+15N，即除以15只能余7，對(duì)于除以15余0，1，2，3，4，5，6，8，9，10，11，12，13，14都屬于錯(cuò)題。除以多

18、個(gè)素因子組成的合數(shù)時(shí)，必須與題中所出現(xiàn)的素因子不產(chǎn)生矛盾，不產(chǎn)生矛盾的標(biāo)準(zhǔn)是除以多個(gè)素因子組成的合數(shù)，必須是同時(shí)滿足題中所出現(xiàn)（合數(shù)所包含的）的素因子的數(shù)。同余的解法當(dāng)你看了在上面的初等解法后，對(duì)同余的解法就簡(jiǎn)單了。例某數(shù)為M，有M/3余2，M/5余3，M/7余2，M/11余3，M/13余2，求M=？這里有M除以3，7，13都余2，因3*7*13=273，即2+273N為滿足除以3，7，13都余2的等差數(shù)列；同理，M除以5，11余3，因5*11=55，即3+55Z等差數(shù)列的數(shù)為滿足除以5和11都余3的等差數(shù)列。于是這里出現(xiàn)了兩個(gè)等差數(shù)列：2+273N和3+55Z，是在2+273N數(shù)列取55項(xiàng)尋找除以55余3的數(shù)呢？還是在3+55Z數(shù)列取273項(xiàng)，尋找除以273余2的數(shù)呢？最好是：在2+273N取11項(xiàng)：2，275，548，821，1094，1367，1640，1913，2186，2459，2732，有136