初等数论中消去余数法的探讨

方小慧　柯炳锐

【摘要】假设有某个数除以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.