同余定理

悠悠 2022-06-17 08:29 201阅读 0赞

# 同余运算及其基本性质 #

100除以7的余数是2，意思就是说把100个东西七个七个分成一组的话最后还剩2个。余数有一个严格的定义：假如被除数是a，除数是b（假设它们均为正整数），那么我们总能够找到一个小于b的自然数r和一个整数m，使得a=bm+r。这个r就是a除以b的余数，m被称作商。我们经常用mod来表示取余，a除以b余r就写成a mod b = r。  
如果两个数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同余）。这三个性质都是显然的。  
同余运算里还有稍微复杂一些的性质。比如，同余运算和整数加减法一样满足“等量加等量，其和不变”。小学我们就知道，等式两边可以同时加上一个相等的数。例如，a=b可以推出a+100=b+100。这样的性质在同余运算中也有：对于同一个模数m，如果a和b同余，x和y同余，那么a+x和b+y也同余。在我看来，这个结论几乎是显然的。当然，我们也可以严格证明这个定理。这个定理对减法同样有效。

**性质：如果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的余数相同。

容易想到，两个同余式对应相乘，同余式两边仍然相等：  
**如果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)。

现在你知道为什么[有的题][Link 1]要叫你“输出答案mod xxxxx的结果”了吧，那是为了避免高精度运算，因为这里的结论告诉我们在运算过程中边算边mod和算完后再mod的结果一样。假如a是一个很大的数，令b=a mod m，那么(a \* 100) mod m和(b \* 100) mod m的结果是完全一样的，这相当于是在a≡b (mod m)的两边同时乘以100。这些结论其实都很显然，因为同余运算只关心余数（不关心“整的部分”），完全可以每一次运算后都只保留余数。因此，整个运算过程中参与运算的数都不超过m，避免了高精度的出现。

在证明[Fermat小定理][Fermat]时，我们用到了这样一个定理：  
**如果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)。

可能以后还要用到更多的定理，到时候在这里更新。

[Link 1]: http://www.vijos.cn/Problem_Show.asp?id=1093
[Fermat]: http://www.matrix67.com/blog/article.asp?id=280