讲义：裴蜀定理 (Bézout's Lemma)
1. 定理陈述
裴蜀定理是数论中关于最大公约数（GCD）的一个重要定理。
内容： 若 $a, b$ 是不全为零的整数，则对于任意整数 $x, y$，代数式 $ax + by$ 都是 $\gcd(a, b)$ 的倍数。 特别地，一定存在整数 $x, y$，使得： $ax + by = \gcd(a, b)$
推论： $a, b$ 互质的充要条件是存在整数 $x, y$ 使得 $ax + by = 1$。
2. 核心工具：带余除法 (Division Algorithm)
在证明之前，我们需要复习带余除法： 对于任何整数 $a$ 和正整数 $d$，一定存在唯一的整数 $q$ (商) 和 $r$ (余数)，使得： $a = qd + r, \quad 0 \le r < d$ 这是证明裴蜀定理的核心动力。
3. 裴蜀定理的证明
我们将通过构造一个集合，并利用“最小数原理”来完成证明。
第一步：构造集合
设 $a, b$ 是不全为 $0$ 的整数。构造一个集合 $S$，包含 $a, b$ 所有正的线性组合： $S = { ax + by \mid ax + by > 0, \text{其中 } x, y \in \mathbb{Z} }$
显然 $S$ 不是空集（例如，如果 $a \neq 0$，则 $a(1) + b(0)$ 或 $a(-1) + b(0)$ 必有一个属于 $S$）。
第二步：选出最小元素
根据最小数原理（任何非空的正整数集合一定有一个最小元素），集合 $S$ 中一定存在一个最小的正整数，我们把它记为 $d$。 因为 $d \in S$，所以一定存在 $x_0, y_0$ 使得： $d = ax_0 + by_0$
第三步：证明 $d$ 是 $a$ 和 $b$ 的公约数
我们要证明 $d \mid a$ 且 $d \mid b$。 利用带余除法，将 $a$ 除以 $d$： $a = qd + r, \quad 0 \le r < d$ 我们要证明余数 $r$ 必须为 $0$。 将 $d = ax_0 + by_0$ 代入上式： $r = a - qd = a - q(ax_0 + by_0) = a(1 - qx_0) + b(-qy_0)$ 观察这个式子，我们发现 $r$ 也是 $a$ 和 $b$ 的线性组合。
- 如果 $r > 0$，那么根据定义 $r$ 应该属于集合 $S$。
- 但是带余除法告诉我们 $r < d$，而 $d$ 是 $S$ 中最小的元素。
- 这产生了矛盾！因此，唯一的可能是 $r = 0$。
既然 $r = 0$，说明 $a = qd$，即 $d \mid a$。同理可证 $d \mid b$。 所以，$d$ 是 $a$ 和 $b$ 的公约数。
第四步：证明 $d$ 是最大公约数
设 $g = \gcd(a, b)$。根据最大公约数的定义： $g \mid a$ 且 $g \mid b$。 那么对于任何线性组合 $ax + by$，根据整除的性质，$g$ 一定能整除它： $$g \mid (ax + by)$$ 由于 $d$ 也是这样一个线性组合（$d = ax_0 + by_0$），所以 $g \mid d$。 因为 $g$ 和 $d$ 都是正整数，且 $g$ 能整除 $d$，所以： $$g \le d$$ 但 $d$ 是公约数，$g$ 是最大公约数，由定义知 $d \le g$。 因此，必然有 $d = g = \gcd(a, b)$。
证毕。
4. 算法实现：如何找到 $x$ 和 $y$？
虽然证明告诉我们 $x, y$ 一定存在，但并没有给出具体数值。在实际计算中，我们使用扩展欧几里得算法 (Extended Euclidean Algorithm)。
示例计算
求 $12x + 42y = \gcd(12, 42)$ 的一组整数解。
-
辗转相除法求 GCD:
- $42 = 3 \times 12 + 6$
- $12 = 2 \times 6 + 0$ 所以 $\gcd(12, 42) = 6$。
-
逆向代回: 由第一个等式得：$$6 = 42 - 3 \times 12$$ 对照 $ax + by = d$：$$42(1) + 12(-3) = 6$$
得到一组解：$x = -3, y = 1$。
5. 总结
- 物理含义：裴蜀定理说明了两个数能“凑”出的最小正整数就是它们的最大公约数。
- 核心逻辑：集合的最小元素 + 带余除法导致的矛盾。
- 应用：它是证明“唯一分解定理”（算术基本定理）的基石，也是求解同余方程的基础。
—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com
