模运算

2024-10-08

以最通俗易懂的方式解析模运算及其应用，包括模运算加减、乘除、互质、同余，以及由此延伸出来的费马小定理、模逆元、欧拉函数、欧几里得算法等。

加减

理解加减法的最好方法就是假设你坐在一辆无限长的火车上，每节车厢有10000个座位，编号从No.0000到No.9999。

每当你从No.9999的座位向前移动1步，你就到达了下一节车厢的第一个座位(No.0000)。

print((9999+1) % 10000)
# 0

同样地，如果你从No.0000的座位向后移动1步，你就到达了上一节车厢的最后一个座位(No.9999)。

print((0-1) % 10000)
# 9999

这就是%(模运算符)具体怎么工作的。 +(加法)表示你需要向前移动多少步； -(减法)表示你需要向后移动多少步；

乘除

理解乘除最好的方法就是把数字看作是一个集合，比如9 = [3, 3]，12 = [2, 2, 3]。

乘法的本质就是把两个集合合并在一起，比如9 * 12 = [2, 2, 3, 3, 3]。

除法的本质就是把两个集合相减， $12 = [2, 2, 3]$ 和 $9 = [3, 3]$ 相减，结果： $\frac{12}{9} = \frac{[2, 2, 3]}{[3, 3]} = \frac{[2, 2]}{[3]}$ 。

基于上述基本事实，可以推导出许多非常有用的定理。

$a \cdot b \mod p = (a \mod p) \cdot (b \mod p) \mod p$
$(x^{a} \mod p)^{b} \mod p = x^{a \cdot b} \mod p$

互质

两个数的最大公约数为1时，这两个数互质。

所有的合数都是由质数相乘得到的。

所以：

对于质数：任意两个都是互质的，因为他们本身就是最小单元
- 比如 $3 = [3]$ 和 $17 = [17]$ 。
对于合数：当组成合数 $a$ $a$ 和 $b$ $b$ 的两个质数集合 $A$ $A$ 和 $B$ $B$ 没有任何共同元素时， $a$ $a$ 和 $b$ $b$ 互质。
- 比如 $8 = [2, 2, 2]$ 和 $15 = [3, 5]$ ，他们没有任何共同元素，所以 $8$ 和 $15$ 互质。

同余

同余就是两个数余数相同，比如 $7 \mod 15 \equiv 22 \mod 15$ ，他俩对15取模之后的结果都是 7。

本质上 $7 + 15 \cdot k \mod 15 \equiv 7 \mod 15$ , $k \in Z$ 。

费马小定理

当 a, p 互质时，有下列公式成立：

a^{p-1} \mod p \equiv 1 \mod p

证明过程可以参考这个视频：

首先证明当 p 和互质时， $a \cdot r \mod p$ , $r \in [1, (p-1)]$ 是对数集 $[1, (p-1)]$ 的重排列。

假设存在 $r_1, r_2 \in [1, p-1], r_1 \ne r_2$ , 使得 $a \cdot r_1 \mod p = a \cdot r_2 \mod p$ ,则：

a \cdot (r_1 - r_2) \mod p \equiv 0 \mod p

明显不存在这样的 $r_1, r_2$ ，证毕。

则：

a^{p-1} \cdot (p-1)! \mod p \equiv （p-1)! \mod p

a^{p-1} \mod p \equiv 1 \mod p

模逆元

当 $a \cdot b \mod p = 1$ 时， $b = a^{-1}$ 就是 a 的模逆元。

用费马小定理可以快速求模逆元：

a\cdot b \mod p = 1

a \cdot b \mod p = a^{p-1} \mod p

b \mod p = a^{p-2} \mod p

举个例子： $a = 7, p = 13$ ，则 $a^{-1} = 7^{13-2} \mod 13 = 2$

用 python 中的 pow函数可以快速计算模逆元。更多求模逆元的方法可以参考algodoc的文章。

欧拉函数

对正整数n，欧拉函数 φ(n) 是小于等于 n 的正整数中与n互质的数的数目。

欧拉函数是费马小定理的延伸，欧拉函数（Euler’s totient function）通常用符号 $\phi(n)$ 表示，它表示小于等于 n 且与 $n$ 互质的正整数的个数。其公式在数学上可以表示为：

定义公式

\phi(n) = n \prod_{p \mid n} \left( 1 - \frac{1}{p} \right)

其中：

$p$ 表示 $n$ 的所有不同的素因子。
$p\mid n$ 表示 $p$ 是 $n$ 的一个因子。

分解步骤

如果 $n$ 的素因子分解为：

n = p_1^{k_1} p_2^{k_2} \cdots p_m^{k_m}

则欧拉函数可以计算为：

\phi(n) = n \left( 1 - \frac{1}{p_1} \right) \left( 1 - \frac{1}{p_2} \right) \cdots \left( 1 - \frac{1}{p_m} \right)

计算示例

对于 $n = 12$ ：

分解 $n = 2^2 \cdot 3^1$ 。
计算：

\phi(12) = 12 \left( 1 - \frac{1}{2} \right) \left( 1 - \frac{1}{3} \right) = 12 \cdot \frac{1}{2} \cdot \frac{2}{3} = 4

因此，欧拉函数 $\phi(12) = 4$ 。

性质

素数的欧拉函数

如果 n = p 是一个素数，则： $\phi(p) = p - 1$

因为所有的数 $1, 2, \ldots, p-1$ 都与 $p$ 互质。

幂次的欧拉函数

如果 $n = p^k$ 且 $p$ 是素数，则： $\phi(p^k) = p^k \left( 1 - \frac{1}{p} \right) = p^k - p^{k-1}$ ，因为 $p^k$ 中被 $p$ 整除的数有 $p^{k-1}$ 个。

乘积性质

如果 $m$ 和 $n$ 互质（即 $\gcd(m, n) = 1$ ），则： $\phi(mn) = \phi(m) \cdot \phi(n)$
例子： $\phi(12) = \phi(3 \cdot 4) = \phi(3) \cdot \phi(4) = 2 \cdot 2 = 4$ 。

累加性质

如果 $n$ 是一个正整数，则所有小于 $n$ 的正整数中互质数的个数加起来为： $\sum_{d \mid n} \phi(d) = n$ ，其中 $d \mid n$ 表示 $d$ 是 $n$ 的一个正因子。
例子：对 $n = 6$ ，其因子为 $1, 2, 3, 6$ ，计算 $\phi(1) + \phi(2) + \phi(3) + \phi(6)$ ： $1 + 1 + 2 + 2 = 6$

费马小定理延伸

a^{\phi(n)} \equiv 1 \pmod{n}\ \text{(如果 \( \gcd(a, n) = 1 \))}

欧几里得算法

欧几里得算法是一种用于计算两个数的最大公约数的算法。它的基本原理是，两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。

证明：

假设 $A > B$ , A 和 B 的最大公约数是 N，则： $C = A - B = N \cdot(a - b)$ ，显而易见 $A, B, C$ 的最大公约数都是 $N$ 。

通过以上不断地求 $C$ ，即可快速算出两个超大数的最大公约数。

模运算

模运算

加减

乘除

互质

同余