两同余式组解的互补定理.docVIP

两同余式组解的互补定理 　　摘要：给出了两个同余式组解间的互补定理，并说明应用此定理可以巧妙地“神奇化易”，利用一个同余式组的解来简单求出另一个同余式组的解. 　　关键词：同余式组解;孙子定理;互补关系 　　中图分类号：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）. 　　证毕. 　　此定理好像是两个同余式组间的一座桥梁，从而方便了直接验证法求解.