两同余式组解的互补定理

王元恒

摘要：给出了两个同余式组解间的互补定理，并说明应用此定理可以巧妙地“神奇化易”，利用一个同余式组的解来简单求出另一个同余式组的解.

关键词：同余式组解;孙子定理;互补关系

中图分类号：O156.1     文献标志码：A     文章编号：1674-9324（2016）42-0198-02

文[1]中给出了一次同余式的四种不同解法.其实，一次同余式在公元前二世纪时因天文历法的需要而出现，同时也出现了同余式组

ax≡r（mod60）≡r（modb）

的求解问题（[2]），其中，a是一回归年日数，b是一朔望月数.

《孙子算经》（成书于公元67—270年之间中）第26问题（[3]）：“今有物不知其数。三三数之剩二，五五数之剩三，七七数之剩二，问物几何？答曰二十三.”原题后给出最小正整数解是23，并给出了具体的解法：三三数之剩二，置一百四十（70×2）;五五数之剩三，置六十三（21×3）;七七数之剩二，置三十（15×2）。并之得二百三十三，以二百一十减之即得。这种解法经后人整理发展即成为世界著名的孙子定理，或者称为中国剩余定理，它比德国大数学家高斯（1777—1855）发表同样的定理大约早1500年.

定理1（孙子定理）（[4]） 设m，…，m（k≥2）是两两互质的正整数，令M=m…m，M=M/m，M：MM≡1（modm），i=1，…，k.则一次同余式组x≡r（modm）≡…≡r（modm）的解为

x≡rMM+…+rMM（modM）.

由此可见，孙子问题求解中的70，21，15就是孙子定理中的MM，MM，MM.

数学问题的解决过程，是一个化未知为已知、化神奇为简易的过程。与有物不知其数类似的问题，在小学数学奥赛中常出现，近年来在招聘公务员考试中也常出现.

例1（2007年山西省招考公务员试题） 几百个糖，若平均分给7个小朋友，则多余3个，若平均分给8个小朋友，则多余6个，若再加3个，则可以平均分给5个小朋友，那么糖的数目可能有（  ）种情况.

A.3种  B.4种  C.5种  D.6种

解1 此题属于求一数，是其满足：7除余3，8除余6，5除余2。由中国剩余定理可求出此数为：120×3+105×6+56×2-280k，当k取1，2，3时，其数小于1000，因此选A正确.

解2 生活中求解问题并不需要这么复杂，只需要计算出7，8，5的公倍数是7×8×5=280，然后用1000÷280的商3就是答案.

华罗庚先师教导我们（[5]）：“神奇化易是坦道，易化神奇不足提.”对于孙子问题，他说：“只要不是白痴，都能解得答案：分析问题中所给的条件，根据条件逐步寻求满足条件的解（数），由三三数之剩二做起：把2记在心里，然后加3，于是有2+3=5，这时满足第一个条件，再加3，即2+3+3=8，这时满足第一个条件，同时也满足第二个条件，现在就不必再加3，而是加[3，5]=15，立即可得8+15=23（为什么要加15，因为15为3，5的最小公倍数），23同时满足问题中的三个条件，是满足条件的最小正整数解.”孙子的神奇妙算问题，华罗庚仅用加法就求出了答案，印证了他老人家“神奇化易是坦道”的名言.或者更简单，直接验证7的倍数加2：2，9，16，23，…即得23为答案.但是，如果当同余式组的解很大时，就不好直接验算时，还有什么另外简单方法吗？其实，本文发现有如下的“互补定理”，可以利用一个同余式组的解来简单求出另一个同余式组的解.

定理2（互补定理） 设m，…，m（k≥2）是两两互质的正整数，令M=m…m，x为同余式组x≡b（modm）≡…≡b（modm）的解，y为同余式组y≡c（modm）≡…≡c（modm）的解.则

x+y≡0（modM）？圳b+c≡0（modm），i=1，…，k.

证明 由孙子定理知x≡∑bMM（modM），

y≡∑cMM（modM）.

所以，x+y≡∑（b+c）MM（modM）.

如果x+y≡0（modM），则x+y≡0（modm），i=1，…，k.又因为？坌j：1≤j≤k，当j≠i时有M≡0（modm），进而MM≡0（modm）;

当j=i时，MM≡1（modm）.故有

0≡x+y≡∑（b+c）MM≡b+c≡0（modm），i=1，…，k，即b+c≡0（modm）.

反之，如果b+c≡0（modm），则

0≡∑（b+c）MM≡x+y≡0（modm）.

j=1，…，k.又因为m，…，m（k≥2）两两互质，所以有x+y≡0（modm…m），即

x+y≡0（modM）.

证毕.

此定理好像是两个同余式组间的一座桥梁，从而方便了直接验证法求解.

例2 今有物不知其数。三三数之剩一，五五数之剩二，七七数之剩五，问物几何？

解1 由孙子定理知，所求的解为

x≡1×70+2×21+5×15≡82（mod 105）.

解2 此问题正是孙子问题的互补问题，由于孙子问题的解是23，所以应用定理2得最小解为105-23=82.

例3（韩信点兵） 传说的是西汉大将韩信刚拜将时，众将官多有不服.一次他到校军场，查点士兵人数.韩信让士兵五五列队余3人，七七列队余2人，八八列队余5人，九九列队余2人，然后询问人数.下级军官故意把人数错报为2395人，韩信听后，哈哈大笑说：“不对。应当是2333人.”使下级将官们大吃一惊，从此对他十分敬佩.

解1 应用孙子定理（较繁的是计算），令

M=5×7×8×9=2520，M1=7×8×9=504，

M2=5×8×9=360，M3=5×7×9=315，

M4=5×7×8=280.

由MM≡1（modm），i=1，2，3，4，m=5，m=7，

m=8，m=9得到

M=4，M=5，M=3，M=1.

所以所求的解为

x≡3×504×4+2×360×5+5×315×3+2×280×1

≡2333（mod2520）

即韩信说的士兵人数应当是2333人.

解2 首先估计下士兵人数在2000人与2500人之间，而M=5×7×8×9=2520，所以应用定理2的互补方法，来考虑“韩信点兵”问题的互补问题.然后，再应用华罗庚先师的“神奇化易”的直接算法：

先在满足第一条件的数列：

2，7，12，17，22，27，…

中找出同时满足其他条件的数.例如同时满足第一、三条件的数是27，而5和8的最小公倍数是40，所以又可在同时满足第一、三条件的数列：

27，67，107，147，187，…

中找出同时满足其他条件的数.数187就同时也满足了第二条件，而5，7，8的最小公倍数是280，所以又可在同时满足第一、二、三条件的数列：

187，187+280，187+2×280，…

中找出同时满足第四条件的数，就是187.

于是应用定理2知道，士兵人数为2520-187=2333人.

显然在具体计算求解时，解法2比较简单，甚至小学生都会求解，我们大学数学师生更应该会求解.

最后应该指出的是，应用定理2（互补定理）在计算机上求解大型同余式组的解时，可以使计算工作量减少一半.

参考文献：

[1]刘耀斌.一次同余式的解法探讨[J].高等数学研究，2012，（4）：79-81.

[2]沈康身.中国剩余定理的历史发展[J].杭州大学学报，1988，（3）：270-282.

[3]闵嗣鹤，严士健.初等数论[M].北京：高等教育出版社，1982.

[4]华罗庚.数论导引[M].北京：科学出版社，1958.

[5]华罗庚.从孙子的“神奇妙算”谈起[M].北京：人民教育出版社，1964.

Complementary Theorem between the Solutions of Two Congruence Groups and Its Applications

WANG Yuan-heng

（Department of Mathematics，Zhejiang Normal University，Jinhua，Zhejiang 321004，China）

Abstract：The complementary theorem between the solutions of two congruence groups is given in this paper.So，one can get the solution of a congruence group from another solution of its complementary congruence group and some examples are given to show this.

Key words：solutions of congruence group;the Chinese remainder theorem;complementation