运算

如果两个数a和b之差能被m整除，那么我们就说a和b对模数m同余（关于m同余）。 比如，100-60除以8正好除尽，我们就说100和60对于模数8同余。它的另一层含义就是说，100和60除以8的余数相同。 a和b对m同余，我们记作a≡b(mod m)。比如，刚才的例子可以写成100≡60(mod 8)。 你会发现这种记号到处都在用，比如和数论相关的书中就经常把a mod 3 = 1写作a≡1(mod 3)。 之所以把同余当作一种运算，是因为同余满足运算的诸多性质。比如，同余满足等价关系。 具体地说，它满足自反性（一个数永远和自己同余）、对称性（a和b同余，b和a也就同余）和传递性（a和b同余，b和c同余可以推出a和c同余）。这三个性质都是显然的。

性质

1、 如果a≡b(mod m)，x≡y(mod m)，则a+x≡b+y(mod m)。 证明：条件告诉我们，可以找到p和q使得a-mp = b-mq，也存在r和s使得x-mr = y-ms。 于是a-mp + x-mr = b-mq + y-ms，即a+x-m(p+r) = b+y-m(q+s)， 这就告诉我们a+x和b+y除以m的余数相同。 2、如果a≡b(mod m)，x≡y(mod m)，则ax≡by(mod m)。 证明：条件告诉我们，a-mp = b-mq，x-mr = y-ms。 于是(a-mp)(x-mr) = (b-mq)(y-ms)， 等式两边分别展开后必然是ax-m(…) = by-m(…)的形式， 这就说明ax≡by(mod m)。 3、如果ac≡bc(mod m)，且c和m互质，则a≡b(mod m) （就是说同余式两边可以同时除以一个和模数互质的数）。 证明：条件告诉我们，ac-mp = bc-mq，移项可得ac-bc = mp-mq，也就是说(a-b)c = m(p-q)。 这表明，(a-b)c里需要含有因子m，但c和m互质，因此只有可能是a-b被m整除，也即a≡b(mod m)。