学习笔记：扩展欧几里得

· · 算法·理论

前置知识1：欧几里得算法（辗转相除法）

\gcd(a,b) = \gcd(b,a \bmod b)

证明

前置知识2：裴蜀定理

如果有 d = \gcd(a,b)，则有整数组 (x,y) 使得 ax + by = \gcd(a,b)。

证明

什么是扩展欧几里得？

根据裴蜀定理，方程ax + by = \gcd(a,b) 一定有一组整数解 (x,y)。

现在我们需要求出符合条件的 (x,y)。

求解

根据已知式子，构造可得：

bx_1 + (a \bmod b)y_1 = \gcd(b,a \bmod b)

根据欧几里得算法，可得：

\gcd(a,b) = \gcd(b,a \bmod b)

等量代换得：

ax + by = bx_1 + (a \bmod b)y_1

我们知道 a \bmod b = a - b \times \lfloor a \div b \rfloor，那么代入式子得：

ax + by = bx_1 + (a - b \times \lfloor a \div b \rfloor)

将含有 a,b 的项放到一起得：

a(x - y_1) - b(x_1 - y - \lfloor a \div b \rfloor y_1) = 0

我们知道 a,b 任意，那么想让两式相减得 0，只能让两括号内的值都为 0。也就是：

x - y_1 = 0 \\ x_1 - y - \lfloor a \div b \rfloor y_1 = 0

化简，得：

x = y_1 \\ y = x_1 - \lfloor a \div b \rfloor y_1

注意到我们可以通过求解 x_1,y_1 来推导出 x,y。

那么我们不妨再次通过欧几里得算法，让原来的 (x,y) 等于现在的 (x_1,y_1)，以此推出 (x_2,y_2) 来求解 (x_1,y_1)。以此类推，不断分解，最终依次向上推得出 x,y 的值。

这样的分解不是无止境的，当某一组 (x_n,y_n) 中 y_n 的系数为 0，x_n 就可以被求出来。而 y_n 一般将它看作 0。

如此，就可以求出 ax + by = \gcd(a,b) 的解了。