学习笔记：扩展欧几里得

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

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

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

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

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

等量代换得：

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

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

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

化简，得：

注意到我们可以通过求解 $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)$ 的解了。