取模运算+同余定理

一、取模运算

1.定义：取模运算：运算结果得到的是一个数除以另一个数的余数。

2.举例：给定两个正整数：被除数 a 和除数 n，a modulo n (缩写为(一般这样写) a mod n)得到的是a/n 的余数。

举个例子：计算表达式 "5 mod 2" 得到 1，因为 5÷2=2...1（5 除以 2 商 2 余1）；而 "9 mod 3" 得到 0，因为 9÷3=3...0；

3.相关性质：

(1)恒等式：

(a mod n) mod n = a mod n

对所有的正数 x 有：nx mod n = 0

如果 p 是一个质数，且不为 b 的因数，此时由费小马定理有：abp−1 mod p = a mod p

(2)分配律：

(a + b) mod n = [(a mod n) + (b mod n)] mod n

ab mod n = [(a mod n)(b mod n)] mod n

d mod (abc) = (d mod a) + a[(d \ a) mod b] + ab[(d \ a \ b) mod c]

c mod (a+b) = (c mod a) + [bc \ (a+b)] mod b - [bc \ (a + b)] mod a

(3)除法定义：

仅当式子右侧有定义时，即 b、n 互质时有：ab mod n = [(a mod n)(b−1 mod n)] mod n，其他情况为未定义的。

(4)乘法逆元：[(ab mod n)(b−1 mod n)] mod n = a mod n.

4.更快的实现：

对2 的 n 次幂的模，可以通过逐位与运算实现(只适用于正数)。即 x % 2n == x & (2n-1) 也可以写为x % 2n == n&((1<

例如：

假定 x 为正数：

x%2 == x&1

x%4 == x&3

x%8 == x&7

二、同余

1.别称：同余定理可以说是同余关系。

2.定义：是指对于一个正整数n，如果a − b整除于n（还有一个等价的条件是它们除以n得出同样的余数），则两个整数a和b被称为同余模n。

一般记作 a≡b(mod n)，读作a同余于b模m，或读作a与b关于模m同余（其中同余于的符号是同余相等符号≡）

例如，5和11同余模3：

11 ≡ 5 (mod 3)

因为11 − 5得出6，它整除于3。或者等价的说，这两个数除以3得到相同的余数：

11 = 3×3 + 2 5 = 1×3 + 2

(以上部分内容来自于维基百科)