初等數論中消去余數法的探討

方小慧　柯炳銳

【摘要】假設有某個數除以a1得到余數b1，除以a2得到余數b2，除以a3得到余數b3……通常《初等數論》教材用孫子定理解決這個問題.孫子定理具有很強的邏輯性和系統性，然而解題步驟通常比較煩瑣，需要把要求的數擴大后再縮小，計算量比較大，中途很可能會出錯.本文介紹的消去余數法，相對孫子定理而言較為簡潔，能夠盡可能縮小計算量，減少出錯的概率，在解答問題的過程中可能還會遇到一些意想不到的巧妙辦法.

【關鍵詞】消去余數法;減法消余法;加法消余法;縮小除數余數法

一、定 義

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

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

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

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

消去余數法在數學競賽中有著不容忽視的作用，減少解題的煩瑣性，本文主要介紹減法消余法，其余兩個實際上是減法消余法的拓展.

二、減法消余法

（一）基本模型

假設有這樣一個數，被a1除余b1，被a2除余b2，被a3除余b3，求這個數字X.

第一步：先用X減去b1，得到一個能夠被a1整除的數，同時這個數被a2，a3除，也會得到新的余數b4，b5;

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

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

第四步：在（X-b1-N1-N2）一定是a1，a2，a3的公倍數，所以可以用式子X-b1-N1-N2=a1×a2×a3×K（K=1，2，3，…），經過轉換便得到X=（b1+N1+N2）a1×a2×a3×K（K=1，2，3，…）.

（二）經典例題的簡便解法

例1 今有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二，問物幾何？

（1）消去余數法

依據題意得：

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

經過調整得：

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

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

下一步則是消去（1+5T2）中的余數1，與此同時也要使得到的新數字能被3、7整除.經過觀察不難得到，（X-2-7×3）這個數字能滿足條件.因為原來的（X-2）能夠被3、7整除，在它的基礎上減去的（7×3），也是3、7的倍數，所以得到的新數字也必能被3、7整除;再看（1+5T2）這一塊，原來是X-2=1+5T2，（X-2）的基礎上減去（7×3=21），21被5除余數是1，因此，（X-2-7×3）能被5整除.用數學式子表示得到：

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

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

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

轉換之后得到：

X=23+105K.

除數余數

3200

5311

7200

以上分析寫成簡單的數學形式則是：

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

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

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

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

故X=23+105k.

（2）孫子定理的解法

設物數為X，依題意得：

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

此時M1=3，M2=5，M3=7;

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

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

得B4=2（35除以3的余數），

B5=1（21除以5的余數），

B6=1（15除以7的余數），

故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 求一個正整數，用3去除X則余數是1，用7去除X則余數是6，用11去除X則余數是5.

（1）消去余數法

根據題意得：

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

觀察不難發現，若是X減去16，則得到一個可以被3和11都能整除的數，因為16=1+3×5=5+11×1，兩個等式相加則成為：

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

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

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

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

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

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

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

除數余數

3100

7641

11500

以上分析寫成簡單的數學形式則是：

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

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

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

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

（2）孫子定理解法摘錄

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

再求7除余1、33除盡的數，用輾轉相除法，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，則對應的數是99.

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

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

X=1 798-231×7=181.

例3 韓信點兵，有兵一隊，若列成五行縱隊，則末行一人;若六行縱隊，則末行五人;若七行縱隊，則末行四人;若十一行縱隊，則末行十人;求兵數.

（1）消去余數法

設兵數是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）孫子定理摘錄

設兵數是X，依題意得：

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

此時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的余數），

M2′=1（385除以6的余數），

M3′=1（330除以7的余數），

M4′=1（210除以11的余數），

故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）.

相對來說，孫子定理需要通過把數字在原理基礎上擴大很多，然后再縮小，計算過程比較煩瑣;減法消余法則通過步步消除余數得到所有除數的公倍數，然后返回來求得原來的X，計算過程相對簡潔.

三、加法消余法

（一）基本模型

假設有這樣一個數，被a1除余b1，被a2除余b2，被a3除余b3，求這個數字X.

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

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

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

第四步：在（X+a1-b1+N1+N2）一定是a1，a2，a3的公倍數，所以可以用式子X+a1-b1+N1+N2=a1×a2×a3×K（K=1，2，3，…），經過轉換便得到X=（b1-a1-N1-N2）+a1×a2×a3×K（K=1，2，3，…）.

（二）經典例題的簡便解法

例4 有物不知數，二二數之余一，三三數之余二，四四數之余三，五五數之余四，六六數之余五，七七數之余六，八八數之余七，九九數之余八，十十數之余九，十一數之余十，十二數之余十一，十三數之余零，求這物數.

（1）消去余數法

除數余數

5400

7600

8700

9800

111000

13010

根據題意得：

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均為整數），

調整得：

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

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

再做調整，（X+1-5×7×8×9×11×10）則能被13整除了.推理過程在例題1已提及.所以得到（X+1-5×7×8×9×11×10）則能被2～13整除.再求出2～13的最小公倍數（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）.

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

四、縮小除數余數法

（一）基本模型

假設有這樣一個數，被A1除余B1，被A2除余B2，被A3除余B3，求這個數字X.

第一步：先對三個除數進行因數分解：A1=a1×n1，A2=a2×n2，A3=a3×n3;

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

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

（二）經典例題的簡便解法

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

（1）消去余數法

根據題意得：

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

在上式的基礎上拆分得到：

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

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）.

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

五、結 論

消去余數法的推算過程，符合同余式性質原理，不必先推導定理，再加以論證，來作為解題依據，其省略寫法既簡便又能令人一目了然，易于理解.消去余數法有機會先后消除若干項余數，更簡化求解過程，是中小學數學競賽解題方法的良好借鑒.

【參考文獻】

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

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

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

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