ExtendedEuclid 扩展欧几里得算法

问题

求两个整数 $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)))$ 。

Last updated 5 years ago