模乘法逆元与裴蜀定理

模乘法逆元的定义

已知整数 $$a$$ 和 $$b$$ 满足 $$b > 0$$ ，且两者互质（即最大公约数 $\gcd(a, b) = 1$ ）。

则必然存在整数 $$x$$ ，满足以下线性同余方程：

a \times x \equiv 1 \pmod b

此时，满足该条件的整数 $$x$$ 称为 $$a$$ 在模 $$b$$ 下的 乘法逆元（Modular Multiplicative Inverse），通常记作：

x \equiv a^{-1} \pmod b

逆元在模 $$b$$ 意义下唯一：若 $$x_1, x_2$$ 均满足上式，则 $a(x_1 - x_2) \equiv 0 \pmod{b}$ 。由于 $\gcd(a, b) = 1$ ，由互质消去律（见下文引理）知 $b \mid (x_1 - x_2)$ ，即 $x_1 \equiv x_2 \pmod{b}$ 。

存在性证明（鸽巢原理 + 反证法）

目标：证明当 $\gcd(a, b) = 1$ 时， $$a$$ 在模 $$b$$ 下的乘法逆元必然存在。

平凡情形：当 $$b = 1$$ 时，任何整数模 $$1$$ 均余 $$0$$ ，同余式 $a \cdot x \equiv 1 \pmod{1}$ 即 $0 \equiv 0$ 恒成立，结论平凡成立。以下设 $b \geq 2$ 。

前置引理：互质消去律

引理（互质消去律）：若 $\gcd(a, b) = 1$ 且 $b \mid k \cdot a$ ，则 $b \mid k$ 。

证明（基于算术基本定理）：

由 $\gcd(a, b) = 1$ 知 $$a$$ 与 $$b$$ 无公共质因子。设 $$b$$ 的质因数分解为 $b = p_1^{e_1} p_2^{e_2} \cdots p_r^{e_r}$ 。由于 $b \mid k \cdot a$ ，每个 $p_i^{e_i}$ 都整除 $k \cdot a$ 。又因为 $\gcd(a, b) = 1$ ，质因子 $$p_i$$ 不出现在 $$a$$ 的分解中，故 $p_i^{e_i}$ 必须整除 $$k$$ 。对所有 $$i$$ 成立，故 $b \mid k$ 。 $\blacksquare$

📌 IMPORTANT

此引理的证明仅依赖算术基本定理（唯一分解定理），不依赖裴蜀定理，从而避免与后续推导产生循环论证。

主定理证明

构造数列：考虑以下 $$b - 1$$ 个正整数的倍数：

1 \cdot a,\quad 2 \cdot a,\quad 3 \cdot a,\quad \ldots,\quad (b-1) \cdot a

将它们分别除以 $$b$$ ，得到对应的余数序列：

r_k = (k \cdot a) \bmod b, \quad k = 1, 2, \ldots, b-1

引理：上述 $$b - 1$$ 个余数两两不同，且均不为 $$0$$ 。

证明（反证法）：

第一步：余数均不为 $$0$$

假设存在某个 $k \in \{1, 2, \ldots, b-1\}$ ，使得 $b \mid k \cdot a$ 。

由互质消去律， $\gcd(a, b) = 1$ 且 $b \mid k \cdot a$ 推出 $b \mid k$ 。

但 $1 \leq k \leq b-1$ ，矛盾。故每个余数均不为 $$0$$ 。

第二步：余数两两不同

假设存在 $i, j \in \{1, 2, \ldots, b-1\}$ 且 $i \neq j$ ，使得：

i \cdot a \equiv j \cdot a \pmod b

则 $b \mid (i - j) \cdot a$ 。由互质消去律， $\gcd(a, b) = 1$ 推出 $b \mid (i - j)$ 。

但 $|i - j| \leq b - 2 < b$ ，矛盾。故各余数两两不同。

结论：

$$b - 1$$ 个余数均属于集合 $\{1, 2, \ldots, b-1\}$ （共 $$b - 1$$ 个元素），且两两不同。由有限集的基数论证（从 $$n$$ 元集到 $$n$$ 元集的单射必为双射，即鸽巢原理的逆否形式），它们恰好是该集合的一个全排列。

特别地，集合中必有某个 $$k$$ 使得：

k \cdot a \equiv 1 \pmod b

这正说明 $$a$$ 在模 $$b$$ 下的乘法逆元 $$x = k$$ 必然存在。 $\blacksquare$

算例

取 $$a = 3$$ ， $$b = 7$$ ，构造数列及其模 $$7$$ 余数：

$$k$$	$k \cdot a$	$k \cdot a \bmod 7$
1	3	3
2	6	6
3	9	2
4	12	5
5	15	1
6	18	4

余数为 $\{3, 6, 2, 5, 1, 4\}$ ，恰好是 $\{1, 2, 3, 4, 5, 6\}$ 的一个全排列。其中 $$k = 5$$ 时余数为 $$1$$ ，故 $3^{-1} \equiv 5 \pmod{7}$ 。

验证： $3 \times 5 = 15 = 2 \times 7 + 1 \equiv 1 \pmod{7}$ 。 $\checkmark$

推广：裴蜀定理（Bézout's Identity）

对任意整数 $$a, b$$ （不全为零），必然存在整数 $$x_0, y_0$$ ，使得： $a \cdot x_0 + b \cdot y_0 = \gcd(a, b)$

证明：

边界与符号处理：若 $$a = 0$$ ，则 $\gcd(0, b) = |b|$ ，取 $x_0 = 0,\ y_0 = \text{sgn}(b)$ 即可； $$b = 0$$ 同理。若 $$a$$ 或 $$b$$ 为负，可先对 $$|a|, |b|$$ 求解后调整 $$x_0, y_0$$ 的符号。以下不妨设 $$a, b > 0$$ 。

第一步：因式分解

令 $M = \gcd(a, b)$ ，则可写：

a = M \cdot k_1, \quad b = M \cdot k_2

其中 $$k_1, k_2 > 0$$ 。由最大公因数的性质知 $\gcd(k_1, k_2) = 1$ 。

第二步：利用互质情形的结论

由上节"存在性证明"，因 $\gcd(k_1, k_2) = 1$ ，所以 $$k_1$$ 在模 $$k_2$$ 下的乘法逆元存在，即存在整数 $$x_0$$ 使得：

k_1 \cdot x_0 \equiv 1 \pmod{k_2}

这等价于： $k_2 \mid (k_1 \cdot x_0 - 1)$ ，即存在整数 $$y_0$$ 使得：

k_1 \cdot x_0 - 1 = -k_2 \cdot y_0

整理得：

k_1 \cdot x_0 + k_2 \cdot y_0 = 1

第三步：还原到原变量

两边同乘 $$M$$ ：

M \cdot k_1 \cdot x_0 + M \cdot k_2 \cdot y_0 = M

代入 $$a = M k_1$$ ， $$b = M k_2$$ ：

\boxed{a \cdot x_0 + b \cdot y_0 = M = \gcd(a, b)}

故裴蜀定理成立。 $\blacksquare$