整数 a 除以整数 b,若得到的余数是 r,则记作
$$a \bmod{b} = r$$
例如
$$5 \bmod{3} = 2$$
$$-5 \bmod{3} = 1$$
模运算的部分性质如下:
$$(a + b) \bmod{c} = ((a \bmod{c}) + (b \bmod{c})) \bmod{c}$$
$$(a \cdot b) \bmod{c} = ((a \bmod{c}) \cdot (b \bmod{c})) \bmod{c}$$
$$a^{b} \bmod{c} = (a \bmod{c})^{b} \bmod{c}$$
如果你对模运算还不太熟悉,推荐先阅读 Khan Academy 的入门课程。
同余
两个整数 a、b,若它们除以正整数 n 所得的余数相等,即 $a \bmod{n} = b \bmod{n}$,则称 a 和 b 对于模 n 同余,记作
$$a\equiv b \pmod{n}$$
读作 a 同余于 b 模 n,或 a 和 b 关于模 n 同余。例如
$$2\equiv 8 \pmod{6}$$
当 k 为整数($k \in \mathbb{Z}$)时,同余关系有如下性质。
$$a\equiv b \pmod{n}\ \ \ \ \Rightarrow \ \ \ \ ak\equiv bk \pmod{n}$$
当 k、n 互质时,有
$$ak\equiv bk \pmod{n}\ \ \ \ \Rightarrow \ \ \ \ a\equiv b \pmod{n}$$
模逆元
参考倒数($xy = 1$)的定义,对整数 a 和 b,若
$$ab \equiv 1 \pmod{n}$$
则称 a 和 b 关于模 n 互为模倒数,也叫数论倒数、模反元素或模逆元(modular multiplicative inverse),还可以记作
$$b \equiv \frac{1}{a} \pmod{n}\ \ \ \ 或\ \ \ \ b \equiv a^{-1} \pmod{n}$$
类似于实数除法,在模 n 下的除法可以用和对应模逆元的乘法来表达。”分数取模”,等价于求分母的模逆元。
当 a、b 关于模 n 互为模逆元时,$b \bmod{n} = \frac{1}{a} \bmod{n}$
$$\frac{c}{a} \bmod{n} = (c \cdot \frac{1}{a}) \bmod{n} = ((c \bmod{n}) \cdot (\frac{1}{a} \bmod{n})) \bmod{n} = ((c \bmod{n}) \cdot (b \bmod{n})) \bmod{n} = (c \cdot b) \bmod{n}$$
例如
$$\frac{20}{3} \bmod{7} = ((20 \bmod{7}) \cdot (\frac{1}{3} \bmod{7})) \bmod{7} = (6 \times 5) \bmod{7} = 2$$
根据定义,求 a 关于模 n 的模逆元,若 b 是解,$k \in \mathbb{Z}$,则 $b + kn$ 也都是解,且最小的非负整数解小于 n,例如
$$2 \times 3 \equiv 1 \pmod{5}$$
$$2 \times 8 \equiv 1 \pmod{5}$$
即 3 和 8 都是 2 关于模 5 的模逆元,其中 3 是最小的非负整数解。所以求模逆元可以通过遍历 0 ~ n 来确定。
# find modular multiplicative inverse of 'a' under modulo 'n' |
但这种方法在 n 取值很大时效率不高。你可以参考文章 Modular multiplicative inverse,使用扩展欧几里得算法或费马小定理改进。
def extended_euclid_gcd(a: int, b: int) -> list: |
已知整数 a、n,使用扩展欧几里得算法可以求出整数 x、y、g 满足下式。
$$ ax + ny = g $$
其中,g 是 a 和 n 的最大公约数。上式两边同模 n,有
$$(ax + ny) \bmod{n} = (ax \bmod{n}) + (ny \bmod{n}) = ax \bmod{n} = g \bmod{n}$$
即
$$ax \equiv g \pmod{n}$$
当 a、n 互质时,$g = 1$,此时 x 就是解。当 $g \neq 1$ 时, a 关于模 n 的模逆元不存在。
两数互质的充分必要条件是两数的最大公约数为 1。也就是说,a 关于模 n 的模逆元存在的充分必要条件是 a 和 n 互质。