模运算规则推导

模运算规则

1.定义

定义: 对于整数 a 和 b, 存在N * b + r = a, 则有模运算a mod b = r

也可以设一个N, N为a/b的整数部分, 表示为a mod b = a - N*b = r

tips: 在本篇博客中, {}表示被隐藏的信息

2.加法运算

证明 (a+X)mod b = (a mod b + X mod b)mod b

设N, 有(a+X)mod b = a+X-N*b = r[1], 又有N*b+r = a+X[1-1]

设N1, 有a mod b = a-N1*b = r1[2], 又有N1*b+r1 = a[2-1]

设N2, 有X mod b = X-N2*b = r2[3], 又有N2*b+r2 = X[3-1]

观察[2-1],[3-1]与[1-1]的关系(注意, r1+r2可能大于等于b, 当r1+r2>=b时, 此时N3>0)

可以设N3, 并令(r1+r2)mod b = r1+r2-N3*b = r[4]

将[2]与[3]带入[4]则有(a mod b + X mod b)mod b = r[5]

将[1]带入[5]则有(a mod b + X mod b)mod b = (a+X)mod b, 证毕

3.乘法运算

(n*a)mod b = (a+a+a+......)mod b = (a mod b + a mod b + a mod b + ......)mod b

tips: …… 意味着 n 个表达式

4.指数运算

(a^n)mod c = (a*a*a*......)mod c = ......

5.对于a^b mod c的快速算法

10^1 mod 3 = [3 * 3 ] + 1

10^2 mod 3 = [33 * 3] + 1

10^3 mod 3 = [333 * 3] + 1

……

11^1 mod 3 = [3 * 3] + 2

11^2 mod 3 = [40 * 3] + 1

11^3 mod 3 = [443 * 3] + 2