同余式

张新春

同余是初等数论的重要组成部分。同余的概念可以说来源于现实。现实生活中有很多周期性变化的事物。比如星期，以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）。……