Question

MOD 运算

Answer 1

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

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

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

运算规律

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

(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满足a mod p = b mod p，则称他们模p相等，记做
a ≡ b (mod p)
可以证明，此时a、b满足 a = kp + b，其中k是某个整数。

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

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