Extended Euclid - 扩展欧几里得算法

问题

求两个整数 $x, y$ ，满足不定方程：

$a \times x + b \times y = gcd(a, b)$

其中 $a, b$ 是正整数， $gcd(a,b)$ 是 $a, b$ 的最大公约数。

解法

扩展欧几里得算法来源于最大公约数的特性，即对于正整数 $a, b$ 的最大公约数 $gcd(a,b)$ ，必然存在整数 $x, y$ 满足本题的等式。

根据上一节Euclid中的迭代式：

$\begin{matrix} a_{0} & = & a \\ b_{0} & = & b \\ \cdots \\ a_{k} & = & b_{k-1} \\ b_{k} & = & a_{k-1} \bmod b_{k-1} \end{matrix}$

存在相应的整数 $x_{k-1}, y_{k-1}, x_{k}, y_{k}$ 满足：

$a_{k-1} \times x_{k-1} + b_{k-1} \times y_{k-1} = gcd(a_{k-1}, b_{k-1}) = gcd(a_{k}, b_{k}) = a_{k} \times x_{k} + b_{k} \times y_{k}$

变换等式得到：

$a_{k-1} \times x_{k-1} + b_{k-1} \times y_{k-1} = b_{k-1} \times x_{k} + (a_{k-1} \bmod b_{k-1}) \times y_{k}$

注意到两正整数的取模运算满足：

$p \bmod q = p - \lfloor \frac{p}{q} \rfloor \times q$

其中 $\lfloor p \rfloor$ 表示向下取整，小于等于 $p$ 的最大整数。

可以推导出：

$a_{k-1} \times x_{k-1} + b_{k-1} \times y_{k-1} = b_{k-1} \times x_{k} + (a_{k-1} - \lfloor \frac{a_{k-1}}{b_{k-1}} \rfloor \times b_{k-1}) \times y_{k}$

将上面等式按照参数 $a_{k-1}, b_{k-1}$ 等式变换，得到：

$a_{k-1} \cdot (x_{k-1}) + b_{k-1} \cdot (y_{k-1}) = a_{k-1} \cdot (y_{k-1}) + b_{k-1} \cdot (x_{k} - \lfloor \frac{a_{k-1}}{b_{k-1}} \rfloor \cdot y_{k})$

由于等式两边括号外的参数完全相同，可得：

$\begin{matrix} x_{k-1} & = & y_{k} \\ y_{k-1} & = & x_{k} - \lfloor \frac{a_{k-1}}{b_{k-1}} \rfloor \cdot y_{k} \end{matrix}$

递归的最后一步 $n + 1$ 时有 $a_{n+1} = b_{n}, b_{n+1} = 0$ 。这时有一组解：

$\begin{matrix} a_{n+1} \times x_{n+1} + b_{n+1} \times y_{n+1} = gcd(a_{n+1}, b_{n+1}) \\ x_{n+1} = 1, y_{n+1} = 0 \end{matrix}$

在辗转相除发计算最大公约数时，每一步中都可以顺带着计算出这一步的 $x, y$ ，最后得到一组解。该算法的时间复杂度约为 $O(log_2 (max(a, b)))$ 。

Extended Euclid - 扩展欧几里得算法

问题

解法

Exgcd

源码

测试