同余式

文︳張新春

同余式

文︳張新春

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

同余式的定義

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

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

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

表示同余的符號“≡”由“數學王子”高斯發明。1801年，年僅24歲的高斯寫就著名的數論專著《算術研究》。在此書中，高斯用這個符號表示同余。他在書中寫道：“今后我將用符號≡表示兩個數的同余式，模則放在括弧內，如-16≡9（mod5）；-7≡15（mod11）?！保ㄐ炱贩剑瑥埣t.數學符號史[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是整數，則ac≡bc（modm）。

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

5.若 a≡b（modm），d 是 a，b 和 m 的公因數，

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

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

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

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

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

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

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

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

首先，我們有如下結論：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的余數都不相同，顯然不可能相等）

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

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

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

游戲的原理是這樣的。

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

數學教育的真功夫是對數學與數學教育的把握，唯此才能成就好的數學課堂。湖南數學教師的老朋友，《湖南教育》的申建春老師開通了微信公眾號“與數學老師談心”，請關注。