同余式

張新春

同余是初等數(shù)論的重要組成部分。同余的概念可以說來源于現(xiàn)實?，F(xiàn)實生活中有很多周期性變化的事物。比如星期，以7天為一個周期，于是考慮10天后是星期幾，只需要考慮3天后是星期幾。再如生肖紀年，以12年為一個周期。2017年是雞年，再過12年還是雞年，而再過30年是什么年，就只要看過6年是什么年就行了。這里10和3對于7，30和6對于12，都具有某種相同的關系。把這種關系抽象出來，就是同余的概念。

同余式的定義

給定一個正整數(shù)m，如果整數(shù)a和b被m除所得的余數(shù)相同，則稱a和b對于模m同余，記作a≡b（modm）。這里的mod是英文modulus的簡寫，讀作模，a≡b（modm）可讀作a和b對于模m同余。

整數(shù)a和b被m除所得的余數(shù)相同，就意味著a和b的差能被m整除。于是a≡b（modm）就意味著有整數(shù)k，使得a-b=km。

這可以理解為同余的另一種等價的定義方式。在以后證明同余的有關性質時，用這個定義將更方便。

表示同余的符號“≡”由“數(shù)學王子”高斯發(fā)明。1801年，年僅24歲的高斯寫就著名的數(shù)論專著《算術研究》。在此書中，高斯用這個符號表示同余。他在書中寫道：“今后我將用符號≡表示兩個數(shù)的同余式，模則放在括弧內，如-16≡9（mod5）；-7≡15（mod11）?！保ㄐ炱贩?，張紅.數(shù)學符號史[M].第338頁.科學出版社，2006.9）

同余式的基本性質

同余式具備如下三條基本性質。

1.反身性，a≡a（modm）；

2.對稱性，若a≡b（modm），則b≡a（modm）；

3.傳遞性，若a≡b（modm），b≡c（modm），則a≡c（modm）。

反身性與對稱性是非常明顯的，我們只證明傳遞性。

事實上，由a≡b（modm）知a-b=km，由b≡c（modm）知b-c=lm。

上述兩式相加，有a-c=（k+l）m。

這就意味著a≡c（modm）。傳遞性得證。

以上性質都與等式的性質完全類似。此外，同余式還具有如下運算性質。

1.若a≡b（modm），c≡d（modm），則a+c≡b+ d（modm）。

2.若a≡b（modm），c≡d（modm），則a-c≡bd（modm）。

3.若a≡b（modm），c≡d（modm），則ac≡bd（modm）。特別地，若a≡b（modm），c是整數(shù)，則ac≡bc（modm）。

4.若a≡b（modm），k>0，則ak≡bk（modmk）。

6.若a≡b（modm），d是m的因數(shù)，則a≡b（modd）。

7.若ac≡bc（modm），且（c，m）=1（即c，m互質），則a≡b（modd）。

8.若a≡b（modm），則an≡bn（modm）。

以上性質的證明不難，只需運用同余的定義即可。而且，這些性質也與等式的一些性質極為相似。需要注意的是，性質7與通常的等式性質不一樣，同余式的兩邊并不是可以任意除以同一個數(shù)的，除非這個數(shù)與?；ベ|。

作為同余的一個應用，我們來討論一下一種“棄九法”的檢驗計算結果的方法。比如，給定一個加法算式2313+5829+7043=15175，我們需要檢驗這個等式是否成立，可以先將加數(shù)的各個數(shù)位上的數(shù)字相加，則有2+3+1+3=9，5+8+2+9=24，7+0+4+3=14。這些和中還有非一位數(shù)，繼續(xù)作類似的加法，有2+4=6，1+4=5。

再將每個加數(shù)通過這種處理后得到的數(shù)加起來，有9+6+5=20。繼續(xù)作加法，得2+0=2。這樣最終得到一個一位數(shù)，我們把這個數(shù)作為加數(shù)的檢驗數(shù)。

用同樣的方法，我們計算和的檢驗數(shù)，有1+5+1+7+5=19。用相同的方法再計算，有1+9=10，1+0=1。得到和的檢驗數(shù)為1，與加數(shù)的檢驗數(shù)不同，因此可以判斷原加法算式是錯誤的。值得注意的是，只有當兩個檢驗數(shù)不相等時，才能應用這種方法判斷計算是否有誤。而當檢驗數(shù)相等時，這種方法得不出什么結論。比如10+11=30，10+11=21。這兩個算式應用“棄九法”會發(fā)現(xiàn)檢驗數(shù)相等，無法做出判斷。事實上第一個算式是錯誤的，而第二個算式是正確的。

我們來說明這種方法為何是有效的。

首先，我們有如下結論：10n≡1（modm）。

再來看算式：2313+5829+7043=15175。

2+3+1+3=9，于是2313≡9（mod9），而9≡0（mod9），從而2313≡0（mod9）；

同樣的道理，有5829≡6（mod9），7043≡5（mod9）。

這樣2313+5829+7043≡0+6+5（mod9），而0+ 6+5=11≡2（mod9），所以2313+5829+7043≡2（mod9）。

但15175≡1+5+1+7+5（mod9），而1+5+1+7+5= 19≡1（mod9），所以15175≡1（mod9）。于是2313+ 5829+7043≠15175。（從上面兩個同余式可以看出，該式左右兩邊除以9的余數(shù)都不相同，顯然不可能相等）

這種方法同樣可以用來檢驗乘法。比如，檢驗271×828=224288。因為271≡1（mod9），828≡0（mod9），所以271×828≡0（mod9）。但224288≡8（mod9），所以271×828≠224288。

以下是一個與“棄九法”原理相關的數(shù)學游戲。這個游戲由甲、乙兩個同學玩。具體程序如下：

甲任意想一個數(shù)（比如1589），為了方便，要求各個數(shù)位上的數(shù)不相同，也不包含數(shù)字“0”。再任意把這個數(shù)重新排列得到一個新數(shù)（如5891），然后將兩個數(shù)相減（大數(shù)減小數(shù)），這里是5891-1589=4302。甲再在4302中去掉一個數(shù)字，比如3，這時得到一個數(shù)402。甲做的以上所有工作都不用告訴乙，只需把最后的數(shù)402告訴乙。乙就能猜出甲最后去掉的數(shù)字是3。

游戲的原理是這樣的。

因此，只要甲把去掉一個數(shù)字后的數(shù)告訴乙，乙若發(fā)現(xiàn)這個數(shù)各個數(shù)位上的數(shù)字之和不是9的倍數(shù)，就可以推算出甲去掉的數(shù)字是多少了。事實上，乙只需考慮這個數(shù)各個數(shù)位上的數(shù)字之和再加多少就是9的倍數(shù)即可，需要加上的數(shù)即是甲去掉的數(shù)。在這上面的游戲中，甲最后告訴乙的數(shù)是402，而4+0+2=6，不是9的倍數(shù)，需增加3才得到9的倍數(shù)，因此甲去掉的數(shù)是3。當然，如果甲給乙的最后的數(shù)是9的倍數(shù)，則甲去掉的數(shù)字可能是0，也可能是9。乙無法判斷到底是0還是9。比如上面的游戲中，若甲去掉0而告訴乙是432，則乙只能說甲去掉的數(shù)字可能是0，也可能是9。endprint