初等數(shù)論中消去余數(shù)法的探討

方小慧　柯炳銳

【摘要】假設(shè)有某個(gè)數(shù)除以a1得到余數(shù)b1，除以a2得到余數(shù)b2，除以a3得到余數(shù)b3……通?！冻醯葦?shù)論》教材用孫子定理解決這個(gè)問(wèn)題.孫子定理具有很強(qiáng)的邏輯性和系統(tǒng)性，然而解題步驟通常比較煩瑣，需要把要求的數(shù)擴(kuò)大后再縮小，計(jì)算量比較大，中途很可能會(huì)出錯(cuò).本文介紹的消去余數(shù)法，相對(duì)孫子定理而言較為簡(jiǎn)潔，能夠盡可能縮小計(jì)算量，減少出錯(cuò)的概率，在解答問(wèn)題的過(guò)程中可能還會(huì)遇到一些意想不到的巧妙辦法.

【關(guān)鍵詞】消去余數(shù)法;減法消余法;加法消余法;縮小除數(shù)余數(shù)法

一、定 義

“消去余數(shù)”，顧名思義，就是把一些余數(shù)b1，b2，b3，…在計(jì)算過(guò)程中通過(guò)加上一些數(shù)或減去一些數(shù)逐步使之消掉，最后得到一個(gè)能被所有除數(shù)a1，a2，a3，…整除的數(shù)，就是它們的公倍數(shù)a1×a2×a3×…×K（K=1，2，3，…），然后再返回去計(jì)算要求的數(shù).這里介紹減法消余法、加法消余法、縮小除數(shù)余數(shù)法三種方法.

（1）減法消余法：用未知數(shù)X連續(xù)減去若干個(gè)數(shù)，使得余數(shù)逐漸被消去，最后得到能被所有除數(shù)整除的數(shù)，也就是它們的公倍數(shù).用數(shù)學(xué)式子表示則得到X-N1-N2-…=a1×a2×a3×…×K（K=1，2，3，…）.

（2）加法消余法：用未知數(shù)X連續(xù)加上若干個(gè)數(shù)，使得余數(shù)逐漸被消去，最后得到能被所有除數(shù)整除的數(shù)，也就是它們的公倍數(shù).用數(shù)學(xué)式子表示則得到X+N1+N2+…=a1×a2×a3×…×K（K=1，2，3，…）.

（3）縮小除數(shù)余數(shù)法：把所有的除數(shù)分解成為兩個(gè)因數(shù)相乘的形式，選擇其中的一個(gè)作為新除數(shù)，再用相對(duì)應(yīng)的余數(shù)除以被選為新除數(shù)的因數(shù)，得到新余數(shù).舉個(gè)例子，除以A1可以分解成a1×n1，如果選擇a1作為新除數(shù)，那么則用原來(lái)的余數(shù)B1除以a1，得到新的余數(shù)b1，就能得到X除以a1余數(shù)是b1.其他數(shù)字算法均一樣.在得到一系列新除數(shù)和新余數(shù)之后，再用減法消余法或加法消余法來(lái)解決問(wèn)題.

消去余數(shù)法在數(shù)學(xué)競(jìng)賽中有著不容忽視的作用，減少解題的煩瑣性，本文主要介紹減法消余法，其余兩個(gè)實(shí)際上是減法消余法的拓展.

二、減法消余法

（一）基本模型

假設(shè)有這樣一個(gè)數(shù)，被a1除余b1，被a2除余b2，被a3除余b3，求這個(gè)數(shù)字X.

第一步：先用X減去b1，得到一個(gè)能夠被a1整除的數(shù)，同時(shí)這個(gè)數(shù)被a2，a3除，也會(huì)得到新的余數(shù)b4，b5;

第二步：在（X-b1）的基礎(chǔ)上再減去一個(gè)整數(shù)N1，N1是a1的倍數(shù)，（N1-b4）則是a2的倍數(shù)，減得的數(shù)便能同時(shí)被a1和a2整除，同時(shí)被a3除得到新的余數(shù)b6;

第三步：在（X-b1-N1）的基礎(chǔ)上再減去一個(gè)整數(shù)N2，N2是a1和a2的倍數(shù)，（N2-b6）則是a3的倍數(shù)，減得的數(shù)便能同時(shí)被a1，a2，a3整除;

第四步：在（X-b1-N1-N2）一定是a1，a2，a3的公倍數(shù)，所以可以用式子X(jué)-b1-N1-N2=a1×a2×a3×K（K=1，2，3，…），經(jīng)過(guò)轉(zhuǎn)換便得到X=（b1+N1+N2）a1×a2×a3×K（K=1，2，3，…）.

（二）經(jīng)典例題的簡(jiǎn)便解法

例1 今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問(wèn)物幾何？

（1）消去余數(shù)法

依據(jù)題意得：

X=2+3T1=3+5T2=2+7T3（T1，T2，T3均為整數(shù)），

經(jīng)過(guò)調(diào)整得：

X-2=3T1=1+5T2=7T3.

在這里（X-2）成為一個(gè)整體，使得兩個(gè)余數(shù)被消掉，也就是（X-2）這個(gè)數(shù)能同時(shí)被3、7整除，同時(shí)被5整除余數(shù)是1.

下一步則是消去（1+5T2）中的余數(shù)1，與此同時(shí)也要使得到的新數(shù)字能被3、7整除.經(jīng)過(guò)觀察不難得到，（X-2-7×3）這個(gè)數(shù)字能滿足條件.因?yàn)樵瓉?lái)的（X-2）能夠被3、7整除，在它的基礎(chǔ)上減去的（7×3），也是3、7的倍數(shù)，所以得到的新數(shù)字也必能被3、7整除;再看（1+5T2）這一塊，原來(lái)是X-2=1+5T2，（X-2）的基礎(chǔ)上減去（7×3=21），21被5除余數(shù)是1，因此，（X-2-7×3）能被5整除.用數(shù)學(xué)式子表示得到：

X-2-7×3=3T4=5T5=7T6.

能夠同時(shí)被3個(gè)數(shù)整除的數(shù)，必然是它們的最小公倍數(shù)的倍數(shù)，也就是3×5×7K（K=1，2，3，…），所以得到：

X-2-7×3=3T4=5T5=7T6=3×5×7K=105K（K=1，2，3，…）

轉(zhuǎn)換之后得到：

X=23+105K.

除數(shù)余數(shù)

3200

5311

7200

以上分析寫成簡(jiǎn)單的數(shù)學(xué)形式則是：

X=2+3T1=3+5T2=2+7T3（T1，T2，T3均為整數(shù)），

X-2=3T1=1+5T2=7T3，

X-2-7×3=3T4=5T5=7T6=3×5×7k（T4，T5，T6均為整數(shù)），

（Tn=1，2，3…;k=1，2，3…），

故X=23+105k.

（2）孫子定理的解法

設(shè)物數(shù)為X，依題意得：

X≡2（mod 3），X≡3（mod 5），X≡2（mod 7），

此時(shí)M1=3，M2=5，M3=7;

B1=2，B2=3，B3=2（其中M為除數(shù)，B為余數(shù)），

得M4=M2×M3=35，M5=M1×M3=21，M6=M1×M2=15，

得B4=2（35除以3的余數(shù)），

B5=1（21除以5的余數(shù)），

B6=1（15除以7的余數(shù)），

故X≡M4×B1×B4+M5×B2×B5+M6×B3×B6≡35×2×2+21×1×3+15×1×2≡233≡233-105×2≡23（mod 105）.

例2 求一個(gè)正整數(shù)，用3去除X則余數(shù)是1，用7去除X則余數(shù)是6，用11去除X則余數(shù)是5.

（1）消去余數(shù)法

根據(jù)題意得：

X=1+3T1=6+7T2=5+11T3（T1，T2，T3均為整數(shù)）.

觀察不難發(fā)現(xiàn)，若是X減去16，則得到一個(gè)可以被3和11都能整除的數(shù)，因?yàn)?6=1+3×5=5+11×1，兩個(gè)等式相加則成為：

X-16=3（T1-5）=11（T3-1）（T1，T3均為整數(shù)），

然后再看（6+7T2）這部分，因?yàn)?6=2+7×2，得到的新數(shù)（X-16）則是被7除余數(shù)為4.等式表示得到：

X-16=3T4=4+7T5=11T6（T4，T5，T6均為整數(shù)）.

下步則考慮如何消除最后一個(gè)余數(shù)4.在（X-16）的基礎(chǔ)上減去一個(gè)數(shù)，得到的新數(shù)要能夠同時(shí)被3、5、7整除.換言之，也就是減去一個(gè)既是3和11的公倍數(shù)，又是被7除余數(shù)為4的數(shù)，才能夠得到它們?nèi)齻€(gè)數(shù)的公倍數(shù).（3×11×5）則是滿足這個(gè)條件的數(shù)，所以得到新的等式：

X-16-3×11×5=3T7=7T8=11T9（T7，T8，T9均為整數(shù)），

（X-16-3×11×5）是它們的公倍數(shù)，因此，也可以用231K（K=1，2，3，…）表示，轉(zhuǎn)換得：

X=181+231K（K=1，2，3，…）

除數(shù)余數(shù)

3100

7641

11500

以上分析寫成簡(jiǎn)單的數(shù)學(xué)形式則是：

X=1+3T1=6+7T2=5+11T3（T1，T2，T3均為整數(shù)），

X-16=3T4=4+7T5=11T6（T4，T5，T6均為整數(shù)），

X-16-3×11×5=3T7=7T8=11T9（T7，T8，T9均為整數(shù)），

X=181+231k（K=1，2，3，…）.

（2）孫子定理解法摘錄

先求3除余1、77除盡的數(shù)，3除77余2，因此，154就是.不必算.

再求7除余1、33除盡的數(shù)，用輾轉(zhuǎn)相除法，33-4×7=5，7-5=2，5=2×2+1，因此，1=5-2×2=5-2×（7-5）=3×5-2×7=3×（33-4×7）-2×7=33×3-14×7，則對(duì)應(yīng)的數(shù)是99.

最后求11除余1、21除盡的數(shù)，11除22余（-1），因此，11×21-21=210就是所求的數(shù).故問(wèn)題的解是：

X=154×1+99×6+210×5=1 798，

X=1 798-231×7=181.

例3 韓信點(diǎn)兵，有兵一隊(duì)，若列成五行縱隊(duì)，則末行一人;若六行縱隊(duì)，則末行五人;若七行縱隊(duì)，則末行四人;若十一行縱隊(duì)，則末行十人;求兵數(shù).

（1）消去余數(shù)法

設(shè)兵數(shù)是X，依題意得：

X≡1（mod 5）≡5（mod 6）≡4（mod 7）≡10（mod 11），

X-11≡0（mod 5）≡5（mod 6）≡0（mod 7）≡10（mod 11），

X-11-5×6×7×10≡0（mod 5）≡5（mod 6）≡0（mod 7）≡0（mod 11）≡0（mod 5×6×7×11），

即得X≡2 111（mod 2 310）.

（2）孫子定理摘錄

設(shè)兵數(shù)是X，依題意得：

X≡1（mod 5）≡5（mod 6）≡4（mod 7）≡10（mod 11），

此時(shí)M1=5，M2=6，M3=7，M4=11;

B1=1，B2=5，B3=4，B4=10.

由M=5×6×7×11=2 310，

得M5=M2×M3×M4=462，

M6=M1×M3×M4=385，

M7=M1×M2×M4=330，

M8=M1×M2×M3=210，

得M1′=2（462除以5的余數(shù)），

M2′=1（385除以6的余數(shù)），

M3′=1（330除以7的余數(shù)），

M4′=1（210除以11的余數(shù)），

故X≡B1×M5×M1′+B2×M6×M2′+B3×M7×M3′+B4×M8×M4′

≡462×2×1+385×1×5+330×1×4+210×1×10

≡6 731≡2 111（mod 2 310）.

相對(duì)來(lái)說(shuō)，孫子定理需要通過(guò)把數(shù)字在原理基礎(chǔ)上擴(kuò)大很多，然后再縮小，計(jì)算過(guò)程比較煩瑣;減法消余法則通過(guò)步步消除余數(shù)得到所有除數(shù)的公倍數(shù)，然后返回來(lái)求得原來(lái)的X，計(jì)算過(guò)程相對(duì)簡(jiǎn)潔.

三、加法消余法

（一）基本模型

假設(shè)有這樣一個(gè)數(shù)，被a1除余b1，被a2除余b2，被a3除余b3，求這個(gè)數(shù)字X.

第一步：先用X加上（a1-b1），得到一個(gè)能夠被a1整除的數(shù)，同時(shí)這個(gè)數(shù)被a2、a3除，也會(huì)得到新的余數(shù)b4、b5;

第二步：在（X+a1-b1）的基礎(chǔ)上再加上一個(gè)整數(shù)N1，N1是a1的倍數(shù)，（N1-a2+b4）則是a2的倍數(shù)，加得的數(shù)便能同時(shí)被a1和a2整除，同時(shí)被a3除得到新的余數(shù)b6;

第三步：在（X+a1-b1+N1）的基礎(chǔ)上再加上一個(gè)整數(shù)N2，N2是a1和a2的倍數(shù)，（N2-a3+b6）則是a3的倍數(shù)，加得的數(shù)便能同時(shí)被a1，a2，a3整除;

第四步：在（X+a1-b1+N1+N2）一定是a1，a2，a3的公倍數(shù)，所以可以用式子X(jué)+a1-b1+N1+N2=a1×a2×a3×K（K=1，2，3，…），經(jīng)過(guò)轉(zhuǎn)換便得到X=（b1-a1-N1-N2）+a1×a2×a3×K（K=1，2，3，…）.

（二）經(jīng)典例題的簡(jiǎn)便解法

例4 有物不知數(shù)，二二數(shù)之余一，三三數(shù)之余二，四四數(shù)之余三，五五數(shù)之余四，六六數(shù)之余五，七七數(shù)之余六，八八數(shù)之余七，九九數(shù)之余八，十十?dāng)?shù)之余九，十一數(shù)之余十，十二數(shù)之余十一，十三數(shù)之余零，求這物數(shù).

（1）消去余數(shù)法

除數(shù)余數(shù)

5400

7600

8700

9800

111000

13010

根據(jù)題意得：

X=1+2T1=2+3T2=3+4T3=4+5T4=5+6T5=6+7T6=7+8T7=8+9T8

=9+10T9=10+11T10=11+12T11=13T12（Tn均為整數(shù)），

調(diào)整得：

X+1=2T1=3T2=4T3=5T4=6T5=7T6=8T7=9T8=10T9=11T10=12T11=13T12+1（Tn均為整數(shù)）.

也就是說(shuō)，除了13以外，其余的數(shù)都能被（X+1）整除，首先計(jì)算出2～12這11個(gè)數(shù)字的最小公倍數(shù)（5×7×8×9×11），所以（X+1-5×7×8×9×11）也能被它們整除，但不能被13整除.

再做調(diào)整，（X+1-5×7×8×9×11×10）則能被13整除了.推理過(guò)程在例題1已提及.所以得到（X+1-5×7×8×9×11×10）則能被2～13整除.再求出2～13的最小公倍數(shù)（5×7×8×9×11×13=360 360），就能得到：

X+1-5×7×8×9×10×22=5×7×8×9×11×13k，

即X=277 199+360 360k（K=1，2，3，…）.

（2）孫子定理解法摘要

X≡3×720 72×4+4×57 480×6+5×45 045×7+8×40 040×8+6×32 760×10（mod 360 360），

X≡8 295 199-360 360×12≡277 199（mod 360 360）.

相比之下，孫子定理需要把數(shù)字計(jì)算得相當(dāng)龐大，比較麻煩;而用加法消余法計(jì)算這道題，則只需要在X的基礎(chǔ)上加上1，就可以把11個(gè)數(shù)的余數(shù)都消掉了，中間能省掉很多計(jì)算的功夫.

四、縮小除數(shù)余數(shù)法

（一）基本模型

假設(shè)有這樣一個(gè)數(shù)，被A1除余B1，被A2除余B2，被A3除余B3，求這個(gè)數(shù)字X.

第一步：先對(duì)三個(gè)除數(shù)進(jìn)行因數(shù)分解：A1=a1×n1，A2=a2×n2，A3=a3×n3;

第二步：推算得到X被a1除得到新的余數(shù)是b1（也就是B1除以a1得到的余數(shù)），同樣的方法可以求出其余兩個(gè)新余數(shù)b2、b3;

第三步：根據(jù)減法消余法或加法消余法求出一個(gè)數(shù)，使得這個(gè)數(shù)成為a1、a2、a3的公倍數(shù)，然后用相同的方法就可以得到要求的數(shù).

（二）經(jīng)典例題的簡(jiǎn)便解法

例5 今有物不知數(shù)，以五累減無(wú)剩，以七百一十五累減之剩十，以二百四十七累減之剩一百四十，以三百九十一累減之剩二百四十五，以一百八十七累減之剩一百零九，總數(shù)若干？

（1）消去余數(shù)法

根據(jù)題意得：

X=5T1=10+715T2=140+247T3=245+391T4=109+187T5（Tn均為整數(shù)）.

在上式的基礎(chǔ)上拆分得到：

X=5T1=10+143×5T2=140+19×13T3=245+23×17T4=109+17×11T5（Tn均為整數(shù)），

X≡0（mod 5）≡10（mod 143）≡7（mod 17）≡7（mod 19）≡15（mod 23），

X-10≡0（mod 5）≡0（mod 143）≡14（mod 17）≡16（mod 19）≡5（mod 23），

X-10-5×143×14≡0（mod 5）≡0（mod 143）≡0（mod 17）≡0（mod 19）≡0（mod 23）≡0（mod 5×143×17×19×23），

故X≡10 020（mod 5 311 735）.

（2）孫子定理解法

X≡10×37 145×49+7×279 565×（-1）+15×230 945×（-1）+7×312 455×（-7）

≡18 201 050-1 956 955-3 810 925-15 310 295

≡-3 717 325

≡10 020（mod 5 311 735）.

同樣的，孫子定理需要把數(shù)字計(jì)算到相當(dāng)龐大，之后再縮小;而本文介紹的方法首先縮小除數(shù)和余數(shù)，減少計(jì)算量，最后一步減去（5×143×14），為了消去17所對(duì)應(yīng)的余數(shù)，卻意外地把19與23所對(duì)應(yīng)的余數(shù)也同時(shí)消掉，原本復(fù)雜煩瑣的計(jì)算立刻簡(jiǎn)化.

五、結(jié) 論

消去余數(shù)法的推算過(guò)程，符合同余式性質(zhì)原理，不必先推導(dǎo)定理，再加以論證，來(lái)作為解題依據(jù)，其省略寫法既簡(jiǎn)便又能令人一目了然，易于理解.消去余數(shù)法有機(jī)會(huì)先后消除若干項(xiàng)余數(shù)，更簡(jiǎn)化求解過(guò)程，是中小學(xué)數(shù)學(xué)競(jìng)賽解題方法的良好借鑒.

【參考文獻(xiàn)】

[1]張文鵬.初等數(shù)論[M].西安：陜西師范大學(xué)出版社，2013.

[2]洪修仁.初等數(shù)論[M].成都：成都科技大學(xué)出版社，1997.

[3]潘承洞，潘承彪.初等數(shù)論：第2版[M].北京：北京師范大學(xué)出版社，2003.

[4]閔嗣鶴，嚴(yán)士健.初等數(shù)論：第2版[M].北京：人民教育出版社，2003.