从模运算到费马
zjxljx99
·
·
算法·理论
从模运算到费马小定理
一、什么是模运算
模运算（modular arithmetic）可以理解为带余除法中的余数运算。
定义：a \bmod p 表示 a 除以 p 所得的余数。
记法说明：
a \equiv b \pmod{p}
读作“a 与 b 在模 p 下同余”，其含义为：
a - b \text{ 能被 } p \text{ 整除}
即存在整数 k，使得：
a - b = kp
例：
7 \equiv 2 \pmod{5}
因为 7 - 2 = 5，而 5 能被 5 整除。
同时这也表示 7 \div 5 的余数是 2。
再看一例：
12 \equiv 2 \pmod{5}
因为 12 - 2 = 10，10 能被 5 整除，即 12 \div 5 余 2。
二、模运算的基本性质
模运算与普通运算最大的不同在于：它只关心“除以 p 后余几”。
乘法同余性质：
若
a \equiv b \pmod{p}
且
c \equiv d \pmod{p}
则
a \cdot c \equiv b \cdot d \pmod{p}
为什么成立？
因为 a = b + k_1p，c = d + k_2p，所以：
ac = (b + k_1p)(d + k_2p) = bd + (bk_2 + dk_1 + k_1k_2p)p
故 ac - bd 是 p 的倍数，即 ac \equiv bd \pmod{p}。
三、“模意义下等于 1”的含义
在模运算中，a \equiv 1 \pmod{p} 表示：
a - 1 = kp \quad \Longrightarrow \quad a = 1 + kp
也就是说，a 除以 p 余 1。
例：
-
6 \equiv 1 \pmod{5}$，因为 $6 \div 5$ 余 $1
-
11 \equiv 1 \pmod{5}$，因为 $11 \div 5$ 余 $1
所有模 p 下等于 1 的数构成如下数列：
1,\; 1+p,\; 1+2p,\; 1+3p,\; \dots
四、逆元（Modular Inverse）
4.1 定义
若存在整数 b，使得
a \cdot b \equiv 1 \pmod{p}
则称 b 为 a 在模 p 下的逆元，记作 a^{-1}。
4.2 与普通倒数的类比
- 普通数域：2 的倒数是 \frac{1}{2}，满足 2 \times \frac{1}{2} = 1
- 模运算中：在模 7 下，2 的逆元是 4，因为 2 \times 4 = 8 \equiv 1 \pmod{7}
因此可写为：
2^{-1} \equiv 4 \pmod{7}
4.3 为什么逆元必须满足“等于 1”
在普通算术中，乘以一个数的倒数可以将该数“消去”：
a \times \frac{1}{a} = 1
而 1 是乘法单位元，任何数乘以 1 保持不变。
在模运算中同理：为了“消去”因子 a，我们需要找到一个数 a^{-1}，使得
a \times a^{-1} \equiv 1 \pmod{p}
这样在后续运算中，1 不会改变任何结果。
五、什么样的数有逆元
5.1 核心定理
定理：整数 a 在模 p 下存在逆元 \iff \gcd(a, p) = 1（即 a 与 p 互质）
5.2 充分性证明（互质 \Rightarrow 有逆元）
若 \gcd(a, p) = 1，则由裴蜀定理（Bézout's identity），存在整数 x, y，使得：
ax + py = 1
两边同时对 p 取模：
ax + py \equiv 1 \pmod{p}
由于 py 是 p 的倍数，模 p 下为 0，因此：
ax \equiv 1 \pmod{p}
故 x 即为 a 的逆元。
5.3 必要性证明（有逆元 \Rightarrow 互质）
若 a 在模 p 下有逆元 b，则：
ab \equiv 1 \pmod{p}
即存在整数 k，使得：
ab - 1 = kp
整理得：
ab - kp = 1
这说明存在整数 b 和 -k 使 a 与 p 的线性组合等于 1，因此 \gcd(a, p) = 1。
5.4 结论
\boxed{\text{有逆元 } \Longleftrightarrow \text{ 互质}}
六、费马小定理（Fermat's Little Theorem）
6.1 定理陈述
若 p 是质数，且整数 a 不被 p 整除（即 \gcd(a, p) = 1），则：
a^{p-1} \equiv 1 \pmod{p}
6.2 证明
第一步：构造集合 S
取集合：
S = \{1, 2, 3, \dots, p-1\}
共有 p-1 个元素。
第二步：用 a 乘以 S 中的所有元素
定义：
aS = \{a \cdot 1,\; a \cdot 2,\; a \cdot 3,\; \dots,\; a \cdot (p-1)\}
同样有 p-1 个元素。
第三步：证明 aS 中的元素模 p 两两不同
反证法。假设存在 i \neq j（1 \le i, j \le p-1），使得：
a i \equiv a j \pmod{p}
则：
a(i - j) \equiv 0 \pmod{p}
即 p \mid a(i - j)。
由于 p 是质数且 p \nmid a，根据欧几里得引理，必有：
p \mid (i - j)
但 i, j \in \{1, 2, \dots, p-1\}，故 |i - j| \le p-2 < p。
唯一能被 p 整除且绝对值小于 p 的整数只有 0，所以：
i - j = 0 \quad \Longrightarrow \quad i = j
与假设矛盾。
因此 aS 中任意两个元素模 p 都不同。
第四步：证明 aS 中不含模 p 为 0 的元素
假设存在 i（1 \le i \le p-1）使得：
a i \equiv 0 \pmod{p}
则 p \mid ai。由于 p 是质数且 p \nmid a，故 p \mid i。
但 1 \le i \le p-1，不可能被 p 整除，矛盾。
因此，aS 模 p 后的所有结果都落在集合 \{1, 2, \dots, p-1\} 中，且互不相同。
由于这个集合只有 p-1 个元素，而 aS 也有 p-1 个元素，所以：
第五步：将所有元素相乘
S 中所有元素的乘积：
1 \times 2 \times 3 \times \dots \times (p-1) = (p-1)!
aS 中所有元素的乘积：
(a \cdot 1) \times (a \cdot 2) \times \dots \times (a \cdot (p-1))
提取公因子 a（共 p-1 个）：
a^{p-1} \times (1 \times 2 \times \dots \times (p-1)) = a^{p-1} \times (p-1)!
第六步：建立同余等式
因为 aS 模 p 后与 S 是同一组数（顺序不同），所以它们的乘积模 p 相等：
a^{p-1} \times (p-1)! \equiv (p-1)! \pmod{p}
第七步：消去 (p-1)!
由于 (p-1)! = 1 \times 2 \times \dots \times (p-1) 中的每个因子都小于 p，均与 p 互质，因此 (p-1)! 与 p 互质，故存在逆元 [(p-1)!]^{-1}。
两边同时乘以该逆元：
a^{p-1} \times (p-1)! \times [(p-1)!]^{-1} \equiv (p-1)! \times [(p-1)!]^{-1} \pmod{p}
化简得：
\boxed{a^{p-1} \equiv 1 \pmod{p}}
6.3 证明完成
至此，费马小定理得证。🎉
七、费马小定理的重要推论：逆元公式
由费马小定理：
a^{p-1} \equiv 1 \pmod{p}
可改写为：
a \times a^{p-2} \equiv 1 \pmod{p}
而逆元的定义是：
a \times a^{-1} \equiv 1 \pmod{p}
比较两式，可得：
a^{p-2} \equiv a^{-1} \pmod{p}
结论：当 p 为质数且 \gcd(a, p) = 1 时，a 的逆元为：
\boxed{a^{-1} \equiv a^{p-2} \pmod{p}}
这个公式在计算模逆元时非常实用，尤其是当 p 较大时，可通过快速幂在 O(\log p) 时间内求得。