裴蜀定理
在数论中，裴蜀等式（英语：Bézout's identity）或裴蜀定理（Bézout's lemma）（或称贝祖等式）是一个关于最大公约数（或最大公约式）的定理。裴蜀定理得名于法国数学家艾蒂安·裴蜀，说明了对任何整数 \(a\) 和 \(b\) 和 \(m\)，关于未知数 \(x\) 和 \(y\) 的线性丢番图方程（称为裴蜀定理） \(ax + by = m\) 有整数解时当且仅当 \(m\) 是 \(a\) 和 \(b\) 的最大公约数 \(d\) 的倍数。裴蜀等式有解时必然有无穷多个整数解，每组解 \(x\) 、 \(y\) 都称为裴蜀数，可用扩展欧几里得算法求得。[1]
特别的，当 \(a\) 和 \(b\) 互质时，裴蜀定理说明了存在整数 \(x\) 和 \(y\) 使得 \(ax + by = 1\)，这是裴蜀定理的一个推论。[1:1]
想要完整理解裴蜀定理，我们首先从最大公约数开始。
1. 辗转相除法
最大公约数（Greatest Common Divisor，GCD）是指能够整除给定整数集合中所有整数的最大的那个数。
设 \(a\) 和 \(b\) 是两个正整数，\(a > b\)，则 \(a\) 和 \(b\) 的最大公约数等于 \(a\) 除以 \(b\) 的余数 \(r\) 和 \(b\) 的最大公约数。即 \(gcd(a, b) = gcd(b, r)\)。
证明：
设 \(a \div b = m \cdots r\) ，则 \(a = mb + r\).设 \(d\) 是 \(a\) 和 \(b\) 的一个最大公约数。
由于 \(d\) 是 \(a\) 的约数，得 \(d\) 是 \(mb + r\) 的约数，又 \(d\) 是 \(b\) 的约数，所以 \(d\) 也是 \(mb\) 的约数，即得 \(d\) 是 \(r\) 的约数。得 \(d\) 是 \(a\) 和 \(r\) 的公约数。
由于 \(b > r\)，\(d\) 是 \(a\) 和 \(b\) 的最大公约数，所以 \(d\) 是 \(b\) 和 \(r\) 的最大公约数。
同理，对于 \(b\) 和 \(r\)，我们可以找到 \(b\) 和 \(r\) 的最大公约数 \(d'\)，\(d'\) 是 \(b\) 和 \(r\) 的最大公约数，所以 \(d'\) 是 \(a\) 和 \(b\) 的最大公约数。
当如此循环往复，直到 \(r = 0\) 时，\(b\) 和 \(r\) 的最大公约数就是 \(b\)，所以 \(d\) 是 \(a\) 和 \(b\) 的最大公约数。
证明结束。
写成公式表示：
\[gcd(a,b) = \begin{cases} a, & b = 0 \\ gcd(b, a\ \text{mod}\ b), & b \neq 0 \end{cases} \]使用递归的方式实现：
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
2. 扩展欧几里得算法
扩展欧几里得算法是求解裴蜀等式的一种算法，它可以在 \(O(\log{n})\) 的时间复杂度内求解裴蜀等式的一组解。
前文已经提到，裴蜀等式 \(ax + by = m\) 有解时当且仅当 \(m\) 是 \(a\) 和 \(b\) 的最大公约数 \(d\) 的倍数。（公式表示：\(ax + by = k \cdot gcd(a, b), k\in \mathbb{Z}\)）
证明[1:2]过程详见维基百科。
我们根据证明可以得到，若裴蜀等式 \(ax + by = m\) 有解，既 \(ax + by = k \cdot gcd(a, b), k\in \mathbb{Z}\)。
根据辗转相除法，我们可以得到：
\[gcd(a, b) = gcd(b, a\ \text{mod}\ b) = gcd(b, a - \lfloor \frac{a}{b} \rfloor b) \](注： 这里得符号 \(\text{mod}\) 表示取模，而不是求余。 但是在 C++ 中，% 表示的是求余，因此下面我们讨论的范围是 \([0, b)\)。 )
展开裴蜀等式，在 \(a,b \in [0, max(a,b))\) , 我们可以得到：
\[\begin{aligned} ax + by &= k \cdot gcd(a, b) \\ bx^{(1)} + (a - \lfloor \frac{a}{b} \rfloor b)y^{(1)} &= k \cdot gcd(b, a\ \text{mod}\ b) \\ &\cdots \end{aligned} \](注： 这里 \(x\) 和 \(y\) 的上标表示第几次迭代的结果，而不是导数或者幂。)
-
当 \(b \neq 0\) 时，根据前文的辗转相除法， \(gcd(a, b) = gcd(b, a\ \text{mod}\ b)\)。由此我们可以得到：
\[\begin{aligned} ax + by = bx^{(1)} + (a - \lfloor \frac{a}{b} \rfloor b)y^{(1)} \\ ax + by = ay^{(1)} + b(x^{(1)} - \lfloor \frac{a}{b} \rfloor y^{(1)}) \\ \end{aligned} \]故得：
\[\begin{aligned} x &= y^{(1)} \\ y &= x^{(1)} - \lfloor \frac{a}{b} \rfloor y^{(1)} \end{aligned} \]继续计算，我们可以得到：
\[\begin{aligned} x^{(1)} &= y^{(2)} \\ y^{(1)} &= x^{(2)} - \lfloor \frac{b}{a} \rfloor y^{(2)} \\ &\cdots \end{aligned} \] -
当 \(b = 0\) 时，我们可以得到：
\[\begin{aligned} ax + by &= k \cdot gcd(a, b) \\ ax &= k \cdot gcd(a, 0) = k \cdot a \\ \end{aligned} \]解得：
\[ x = k \\ y = 0 \]
令上述递推式中的 \(k = 1\)，我们即可得到裴蜀等式的一组解。
// @param a, b: 两个正整数
// @param x, y: 一组解，利用引用带出递归函数
// @return: a 和 b 的最大公约数
int ExGcd(int a, int b, int &x, int &y)
{
if (b == 0) // 递归边界 b = 0
{
x = 1;
y = 0;
return a;
}
// 递归求解
// 1. 计算 x1, y1
int r = ExGcd(b, a % b, x, y); // 递归求解gcd(b, a % b)
int x1 = x; // 保存 x1
x = y; // 更新 x
y = x1 - a / b * y; // 用y1和x1更新y
return r;
}
个人见解，谨慎参考。
欢迎讨论！
维基百科编者. 貝祖等式[G/OL]. 维基百科, 2023(20231104)[2023-11-04]. https://zh.wikipedia.org/w/index.php?title=貝祖等式&oldid=79621447. ↩︎ ↩︎ ↩︎