模运算的基本性质

令$ a=qm+r,q,m,r\in Z $

加法性质

$ a\mod m+b\mod m\equiv (a+b)\mod m $

$ a\mod m+b\mod m=(q_1m+r_1+q_2m+r_2)\mod m=((q_1+q_2)m+(r_1+r_2))\mod m=r_1+r_2 $

$ (a+b)\mod m =(q_1m+r_1+q_2m+r_2)\mod m=((q_1+q_2)m+(r_1+r_2))\mod m=r_1+r_2 $

模可以分配到加法里，也可以从加法里提取出来，这就是分配律和结合律

乘法性质

$ a\mod m b\mod m\equiv (ab)\mod m $

$ (a\mod m *b\mod m)\mod m=r_1r_2 $

$ (a*b)\mod m=(q_1m+r_1)(q_2m+r_2)\mod m=(m(q_1q_2m+q_1r_2+q_2r_1)+r_1r_2)\mod m=r_1r_2 $

幂运算性质

$ (a^k)\equiv ((a\mod m)^k)\mod m $

根据二项式定理可得：$ T_{p+1}=C_k^p(pm)^{k-p}r^p $

$ \begin{aligned}(qm+r)^k&=\sum_{p=0}^{k} C_k^p(pm)^{k-p}r^p\&=C_k^0(pm)^{k}r^0+C_k^1(pm)^{k-1}r^1+\cdots + C_k^k(pm)^{0}r^k\&=r^k+\underbrace{C_k^0(pm)^{k}r^0+C_k^1(pm)^{k-1}r^1+\cdots + C_k^k(pm)^{1}r^{k-1}}_{所有项都含有因子m}\end{aligned} $

所以$ (a^k)\mod m=r^k $

$ ((a\mod m)^k)\mod m=(r^k)\mod m=r^k $

因此$ (a^k)\equiv ((a\mod m)^k)\mod m $

传递性

若$ a\equiv b(\mod m) $，则$ f(a)\equiv f(b)(\mod m) $

只要f是由加减乘幂构成的表达式就可以替换

同余传递性

如果$ a\equiv b(\mod m) $，且$ c\equiv d(\mod m) $

则

$ a+c\equiv (b+d)(\mod m) $

$ a-c\equiv (b-d)(\mod m) $

$ ac\equiv (bd)(\mod m) $

取模分配律（可以提前或延后取模）

$ a+b\equiv ((a\mod m)+(b\mod m))\mod m $

$ a-b\equiv ((a\mod m)-(b\mod m))\mod m $

$ ab\equiv ((a\mod m)(b\mod m))\mod m $

数学同余理论

给定整数a，b和正整数m，如果a-b能被m整除，则称a和b模m同余，记作：

$ a\equiv b(\mod m) $

等价表述：

$ a=b+km $（其中k是整数）

同余关系性质

1.自反性

$ a\equiv a(\mod m) $

2.对称性

若$ a\equiv b(\mod m) $，则$ b\equiv a(\mod m) $

3.传递性

若$ a\equiv b(\mod m)且b\equiv c(\mod m) $，则$ a\equiv c(\mod m) $

原文链接：https://www.yuque.com/fragrantveget/ucxpnh/qvoa3zrzhc5ovi5u?singleDoc# 《模运算的基本性质》