同余式

张新春

同余是初等数论的重要组成部分。同余的概念可以说来源于现实。现实生活中有很多周期性变化的事物。比如星期，以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）。”（徐品方，张红.数学符号史[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）。

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。endprint