欧几里得算法与扩展欧几里得算法：原理、证明及实现

1 欧几里得算法

1.1 定义与基本符号

设 $a, b$ 为不全为0的正整数， $\gcd(a, b)$ 表示 $a$ 与 $b$ 的最大公约数。

对 $a, b$ 做带余除法：

$a = q\cdot b + r,\quad 0\le r < b$

其中 $q = \lfloor \frac{a}{b} \rfloor$ 为商， $r = a \bmod b$ 为余数。

1.2 核心引理

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

1.3 严格证明

证明思路：证明 $a,b$ 与 $b,r$ 的公约数集合完全相等，则其最大元素相等。

设 $d$ 为 $a,b$ 的任意公约数，即 $d\mid a$ 且 $d\mid b$ 。

由整除的线性性质：若 $d\mid m$ 且 $d\mid n$ ，则对任意整数 $k,l$ 有 $d\mid (km+ln)$ 。

由 $r = a - qb$ ，得 $d\mid r$ ，故 $d$ 为 $b,r$ 的公约数。

反之，设 $d$ 为 $b,r$ 的任意公约数，即 $d\mid b$ 且 $d\mid r$ 。

由 $a = qb + r$ ，得 $d\mid a$ ，故 $d$ 为 $a,b$ 的公约数。

因此：

${d\mid d\mid a \land d\mid b} = {d\mid d\mid b \land d\mid r}$

两集合最大元素相等，即 $\gcd(a,b)=\gcd(b,a\bmod b)$ 。

1.4 算法终止条件

当 $b=0$ 时， $\gcd(a,0)=a$ ，此时 $a$ 即为最大公约数。

1.5 算法实现（C++）

// 递归实现
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

// 迭代实现
int gcd_iter(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

2 扩展欧几里得算法

2.1 数学基础：贝祖定理

对任意不全为0的整数 $a,b$ ，存在整数 $x,y$ 使得：

$ax + by = \gcd(a,b)$

扩展欧几里得算法在求解 $\gcd(a,b)$ 的同时，可求出一组整数解 $(x,y)$ 。

2.2 递推关系推导

设：

$ax_1 + by_1 = \gcd(a,b)$

令 $r=a\bmod b$ ，由欧几里得算法：

$bx_2 + ry_2 = \gcd(b,r) = \gcd(a,b)$

将 $r = a - \lfloor \frac{a}{b} \rfloor \cdot b$ 代入上式：

$bx_2 + (a - \lfloor \tfrac{a}{b} \rfloor \cdot b)y_2 = \gcd(a,b)$

整理得：

$a\cdot y_2 + b\cdot (x_2 - \lfloor \tfrac{a}{b} \rfloor y_2) = \gcd(a,b)$

对比系数可得递推公式：
$\begin{cases}x_1 = y_2 \\ y_1 = x_2 - \lfloor \tfrac{a}{b} \rfloor \cdot y_2 \end{cases}$

2.3 递归终止条件

当 $b=0$ 时， $\gcd(a,0)=a$ ，方程 $a\cdot1 + 0\cdot0 = a$ 成立，即：

$x=1,\ y=0$

2.4 算法实现（C++）

// 返回gcd(a,b)，x、y为引用传参，存储方程解
int exgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    int g = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return g;
}

3 欧几里得算法与扩展欧几里得算法的关联

1. 二者共用同一辗转相除框架，扩展欧几里得是对欧几里得算法的直接扩展；

2. 欧几里得仅求解最大公约数，扩展欧几里得额外求解贝祖方程的整数解；

3. 时间复杂度一致，均为 $O(\log\min(a,b))$ ；