本课时有配套视频讲解，购买后即可观看（永久有效）
裴蜀定理
一、课上练习
编程练习
- 裴蜀定理：L49964
二、知识总结
✨ 核心思想
裴蜀定理（Bezout's Identity）揭示了最大公约数与线性组合之间的深刻联系：对于任意整数 a, b，它们的线性组合 ax + by 所能表示的最小正整数恰好就是 gcd(a, b)。反过来说，ax + by 能表示的值恰好是 gcd(a, b) 的所有倍数。
✨ 定理内容
裴蜀定理：设 a, b 为不全为零的整数，则存在整数 x, y 使得：
ax + by = gcd(a, b)
更一般地，对于整数 c，方程 ax + by = c 有整数解的充要条件是 gcd(a, b) | c。
推论：
- a, b 互素的充要条件是存在整数 x, y 使得 ax + by = 1
- 若 gcd(a, b) = d，则 gcd(a/d, b/d) = 1
- 对于 n 个整数 a₁, a₂, ..., aₙ，它们的线性组合能表示的最小正整数为 gcd(a₁, a₂, ..., aₙ)
✨ 定理证明
证明：设 S = {ax + by | x, y 为整数, ax + by > 0}。
- 因为 a, b 不全为零，所以 S 非空
- 设 d 是 S 中的最小正整数，即 d = ax₀ + by₀
- 对任意 ax + by ∈ S，做带余除法：ax + by = qd + r，其中 0 ≤ r < d
- r = (ax + by) - q(ax₀ + by₀) = a(x - qx₀) + b(y - qy₀)
- 若 r > 0，则 r ∈ S 且 r < d，与 d 的最小性矛盾。所以 r = 0
- 因此 d | (ax + by) 对任意 x, y 成立
- 取 x=1, y=0 得 d | a；取 x=0, y=1 得 d | b。所以 d | gcd(a,b)
- 又 gcd(a,b) | a 且 gcd(a,b) | b，所以 gcd(a,b) | (ax₀ + by₀) = d
- 因此 d = gcd(a, b)
✨ 代码实现
验证裴蜀定理与求解系数
1#include <iostream>
2using namespace std;
3typedef long long ll;
4
5// 扩展欧几里得算法
6// 求 ax + by = gcd(a, b) 的一组特解 (x, y)
7ll exgcd(ll a, ll b, ll &x, ll &y) {
8 if (b == 0) {
9 x = 1; y = 0;
10 return a;
11 }
12 ll d = exgcd(b, a % b, y, x);
13 y -= (a / b) * x;
14 return d;
15}
16
17// 判断方程 ax + by = c 是否有解
18// 如果有解，返回一组特解
19bool solve(ll a, ll b, ll c, ll &x, ll &y) {
20 ll d = exgcd(a, b, x, y);
21 if (c % d != 0) {
22 return false; // 无解
23 }
24 // 将特解从 ax+by=d 调整到 ax+by=c
25 x *= c / d;
26 y *= c / d;
27 return true;
28}
29
30int main() {
31 ll a, b, c;
32 cin >> a >> b >> c;
33
34 ll x, y;
35 if (solve(a, b, c, x, y)) {
36 cout << "有解: x = " << x << ", y = " << y << endl;
37 // 验证
38 cout << "验证: " << a << " * " << x << " + "
39 << b << " * " << y << " = " << a * x + b * y << endl;
40
41 // 通解为 x' = x + (b/d)*t, y' = y - (a/d)*t
42 ll d = __gcd(abs(a), abs(b));
43 cout << "通解: x = " << x << " + " << b / d << "t, "
44 << "y = " << y << " - " << a / d << "t" << endl;
45 } else {
46 cout << "无解" << endl;
47 }
48 return 0;
49}多个整数的裴蜀定理
1#include <iostream>
2#include <cmath>
3using namespace std;
4typedef long long ll;
5
6// n 个整数的线性组合能表示的最小正整数
7// 等于它们的 gcd
8int main() {
9 int n;
10 cin >> n;
11 ll g = 0;
12 for (int i = 0; i < n; i++) {
13 ll a;
14 cin >> a;
15 g = __gcd(g, abs(a));
16 }
17 cout << "这 " << n << " 个数的线性组合能表示的最小正整数为: " << g << endl;
18
19 ll c;
20 cout << "输入目标值 c: ";
21 cin >> c;
22 if (c % g == 0) {
23 cout << c << " 可以被表示" << endl;
24 } else {
25 cout << c << " 不可以被表示" << endl;
26 }
27 return 0;
28}✨ 应用示例
示例 1：判断 12x + 8y = 10 是否有整数解
gcd(12, 8) = 4，而 10 % 4 = 2 ≠ 0，所以无解。
示例 2：求 6x + 15y = 9 的所有整数解
gcd(6, 15) = 3，9 % 3 = 0，有解。
先解 6x + 15y = 3：用扩展欧几里得得 x₀ = -2, y₀ = 1（验证：6×(-2)+15×1 = 3）
再乘以 9/3 = 3：x₁ = -6, y₁ = 3（验证：6×(-6)+15×3 = 9）
通解：x = -6 + 5t, y = 3 - 2t（t 为任意整数）
示例 3：互素性判断
判断 a = 14 与 b = 15 是否互素：
尝试求 14x + 15y = 1。gcd(14, 15) = 1，有解。
exgcd 得 x = -1, y = 1（14×(-1) + 15×1 = 1），所以 14 和 15 互素。
✨ 解题步骤详解
- 识别问题：看到形如 ax + by = c 的等式，考虑裴蜀定理
- 判断有解性：计算 gcd(a, b)，检查 gcd(a, b) | c
- 求特解：用扩展欧几里得求 ax + by = gcd(a,b) 的特解，再乘以 c/gcd(a,b)
- 写出通解：x = x₀ + (b/d)t, y = y₀ - (a/d)t
- 处理额外约束：如非负整数解，从通解中筛选满足条件的 t 范围
✨ 常见错误
- 忘记裴蜀定理的前提是 a, b 不全为零
- 将"有整数解"等同于"有非负整数解"——裴蜀定理保证的是整数解
- 通解公式中 b/d 和 a/d 的符号弄反
- 多个整数的情况忘记对绝对值取 gcd（处理负数）
- 扩展欧几里得递归中 y 的更新公式写错
✨ 总结
裴蜀定理是数论中一个基础而优雅的定理，它将最大公约数与线性组合联系起来。在竞赛中，它常用于：
- 判断可行性：判断某个值能否被若干个数线性组合出来
- 求解线性方程：配合扩展欧几里得算法求具体解
- 互素证明：证明两数互素等价于存在线性组合等于 1
- 不定方程：为更复杂的不定方程问题提供理论基础