mod运算，即求余运算，是在整数运算中求一个整数 x 除以另一个整数y的余数的运算，且不考虑运算的商。在计算机程序设计中都有MOD运算，其格式为： mod(nExp1,nExp2)，即是两个数值表达式作除法运算后的余数。

模p运算

给定一个正整数p，任意一个整数n，一定存在等式
n = kp + r其中k、r是整数，且 0 ≤ r < p，称呼k为n除以p的商，r为n除以p的余数

p是除数 k 相当于商 n相当于被除数 r 相当于余数
余数一定是比除数小的 ,即r<p

对于正整数p和整数a,b，定义如下运算：

• 取模运算：a mod p 表示a除以p的余数。
• 模p加法：(a + b) mod p ，其结果是a+b算术和除以p的余数，也就是说，(a+b) = kp +r，则 (a+b) mod p = r。
• 模p减法：(a-b) mod p ，其结果是a-b算术差除以p的余数。
• 模p乘法：(a × b) mod p，其结果是 a × b算术乘法除以p的余数。

运算规律

结合律	((a+b) mod p + c)mod p = (a + (b+c) mod p) mod p ((a×b) mod p×c)mod p = (a× (b×c) mod p) mod p
交换律	(a + b) mod p = (b+a) mod p (a × b) mod p = (b × a) mod p
分配律	((a +b)mod p × c) mod p = ((a × c) mod p + (b × c) mod p) mod p (a×b) mod c=(a mod c * b mod c) mod c (a+b) mod c=(a mod c+ b mod c) mod c (a-b) mod c=(a mod c- b mod c) mod c

证明((a+b) mod p + c) mod p = (a + (b+c) mod p) mod p
假设
a = k1p + r1
b = k2p + r2
c = k3p + r3
a+b = (k1 + k2) p + (r1 + r2)
如果(r1 + r2) >= p ，则
(a+b) mod p = (r1 + r2) -p
否则
(a+b) mod p = (r1 + r2)
如果(r1 + r2) >= p,将 (a+b) mod p = (r1 + r2) -p 带入
(1) 那么 (a+b) mod p + c = (r1 + r2) -p + k3p + r3 = r1+r2+r3+(k3-1)p
如果(r1+r2)<p ,将(a+b) mod p = (r1 + r2) 带入
(2) 那么(a+b) mod p + c = r1+r2+ k3p + r3 = r1+r2+r3 +k3p
综合(1)(2)两处, ((a+b) mod p + c) mod p的结果是 r1+r2+r3的算数和除以p的余数
同理右边一样的算法可证.

证明((a\*b) mod p\* c)mod p = (a\* (b\*c) mod p) mod p
假设
a = k1*p + r1
b = k2*p + r2
c = k3*p + r3
a*b = ( k1*p + r1)(k2*p + r2) = k1k2p²+(k1r2+k2r1)p+r1r2=(k1k2p+k1r2+k2r1)p+r1*r2;
如果r1*r2 >=p ,则
(ab) mod p = r1*r2 -m*p (m>0 ,属于正整数)
否则r1*r2 < p,则
(a*b) mod p = r1*r2
如果r1*r2 >=p ,那么将(a*b) mod p 带入
(1) 那么 (ab) mod p * c = ( r1*r2 -mp)(k3*p + r3) =( -mk3p+r1r2k3-mk3)p + r1r2r3 ( (m>0 ,属于正整数))
如果r1r2<p 那么将(a*b) mod p带入
(2)那么 (ab) mod p * c = r1r2(k3p+r3)=k3r1r2p+r1r2r3
综合(1)(2)两处 ((a*b) mod p* c)mod p 的结果是 r1r2r3的算术乘积除以p的余数
同理右边一样的算法

这里交换律一看就能看出来不证明了

证明((a +b)mod p × c) mod p = ((a × c) mod p + (b × c) mod p) mod p
假设
a = k1*p + r1
b = k2*p + r2
c = k3*p + r3
证明左边
a+b = (k1 + k2) p + (r1 + r2)
如果(r1 + r2) >= p ，则
(a+b) mod p = (r1 + r2) -p
否则
(a+b) mod p = (r1 + r2)
如果(r1 + r2) >= p,将 (a+b) mod p = (r1 + r2) -p 带入
(1) 那么(a +b)mod p × c =( r1+r2-p)×( k3×p + r3) =( -k3×p+r1k3+r2k3-k3)×p + (r1+r2)×r3
如果(r1+r2)<p ,将(a+b) mod p = (r1 + r2) 带入
(2) 那么(a+b) mod p × c =( r1+r2) ×( k3*p + r3) = (r1k3+r2k3) p +(r1+r2)×r3
综合(1)(2)两处, ((a+b) mod p × c) mod p的结果是(r1+r2)×r3的算数值 除以p的余数
证明右边
(a × c) = (k1p+r1)(k3p+r3) =( k1k3p+k1r3+r1k3) p + r1r3;
如果r1r3>=p ,则
(a × c) mod p = r1r3-mp (m>0的正整数)
如果 r1r3<p ,则
(a × c) mod p = r1r3
同理 (b × c) mod p
如果r2r3>=p ,则 (b × c) mod p = r2r3-np (n>0的正整数)
如果r2r3<p ,则 (b × c) mod p = r2r3
排列组合 四种情况
第一种情况 r1r3>=p && r2r3>=p
那么(a × c) mod p + (b × c) mod p = r1r3-mp + r2r3-np = (-m-n)p+ (r1+r2)r3
第二种情况 r1r3<p && r2r3>=p
那么(a × c) mod p + (b × c) mod p = r1r3 + r2r3-np = (-n)p+ (r1+r2)r3
第一种情况 r1r3>=p && r2r3<p
那么(a × c) mod p + (b × c) mod p = r1r3-mp + r2r3 = (-m)p+ (r1+r2)r3
第二种情况 r1r3<p && r2r3<p
那么(a × c) mod p + (b × c) mod p = r1r3 + r2r3 = (r1+r2)r3
以上四种情况的结果都是(r1+r2)×r3的算数值 除以p的余数 和左边的结果相等

证明(a×b) mod c=(a mod c * b mod c) mod c
假设
a = k1*p + r1
b = k2*p + r2
c= p
(a × b) mod c 的结果有两种情况.(在上面证明过)
如果r1r2>=p ,那么(a × b) mod c = r1r2-mc (m>0)
如果r1r2< p ,那么 (a × b) mod c = r1r2
以上两种的结果都是r1r2乘积 除以c (也是p)的余数.
证明右边
amodc = amodp = r1;
bmodc =bmodp = r2;
a mod c * b mod c = r1*r2;
因此和左边是相等的.

(a+b) mod c=(a mod c+ b mod c) mod c 和(a-b) mod c=(a mod c- b mod c) mod c的证明和(a×b) mod c=(a mod c * b mod c) mod c证明一样,略

模p相等

如果两个数a、b满足a mod p = b mod p，则称他们模p相等，记做
a ≡ b (mod p)
可以证明，此时a、b满足 a = kp + b，其中k是某个整数。

证明
假设
a = k1p+r1;
b = k2p+ r2;
如果 a mod p = b mod p ,那么r1 = r2;
所以 a= k1p+ r1= k1p+b-k2p = (k1-k2)p + b;
因此 a = kp+b;

对于模p相等和模p乘法来说，有一个和四则运算中迥然不同的规则.
在四则运算如果c是一个非0整数，则ac = bc 可以得出 a =b
但是在模p运算中，这种关系不存在. 举例如下

(3 x 3) mod 9 = 0
(6 x 3) mod 9 = 0
但是
3 mod 9 = 3
6 mod 9 =6

那么如何才能消除呢?执行消除需要满足定理条件
定理（消去律）：如果gcd(c,p) = 1 ，则 ac ≡ bc mod p 可以推出 a ≡ (b mod p)

gcd 函数解释
GCD函数是 返回两个或多个整数的最大公约数
最大公约数是能分别将各个参数除尽的最大整数。
例如 2 和4的最大公约数是 2, 2和3的最大公约数是1
gcd(c,p)=1 ,表示没有公约因子

证明
因为ac ≡ bc (mod p)
所以ac = bc + kp，也就是c(a-b) = kp  (模等可以这样转换)
因为c和p没有除1以外的公因子，因此上式要成立必须满足下面两个条件中的一个
1) c能整除k    
2) a = b
第一种情况  ,a-b = kp/c; 因为c和p没有除1以外的公因子, 所以 a-b = k1p;  k1 = k/c  .所以 a = b+k1p ; 所以  a ≡ b (mod p)
第二种情况 a = b，则a ≡ b mod p 显然成立