扩展欧几里得算法公式推导与Python实现

扩展欧几里得算法是一种用于求解两个整数 $a$ 和 $b$ 的最大公约数（GCD）及其系数 $x$ 和 $y$ 的算法，使得满足贝祖等式（Bézout's identity）：
$$ ax + by = \text{GCD}(a, b) $$

一、什么是GCD？

GCD，全称是“Greatest Common Divisor”，也就是最大公约数。两个数的最大公约数是指能够同时整除这两个数的最大整数。例如，对于数字8和12，它们的公约数是1, 2, 4，其中最大的公约数是4，因此GCD(8, 12) = 4。

二、什么是贝祖等式？

贝祖等式是一种数学表达式，它表明对于任何两个整数 $a$ 和 $b$，如果它们的最大公约数是 $d$，那么一定存在整数 $x$ 和 $y$，使得：
$$ ax + by = d $$
这里的 $x$ 和 $y$ 可以是任意整数（包括负数）。

简单地说，贝祖等式告诉我们，对于两个数 $a$ 和 $b$，我们可以找到两个整数 $x$ 和 $y$，使得 $a$ 和 $b$ 的线性组合等于它们的最大公约数。

三、欧几里得算法求GCD

欧几里得算法是一种用于计算两个整数的GCD的高效方法，基于以下原理：
$$ \text{GCD}(a, b) = \text{GCD}(b, a \% b) $$
其中，\% 表示取模运算，a % b 是 a 除以 b 的余数。

步骤：

1. 若 $ b = 0 $，则 $ \text{GCD}(a, b) = a $。
2. 否则，令 $ a $ 为 $ b $，$ b $ 为 $ a \% b $，重复步骤1。

例如，计算GCD(30, 20)的过程如下：

• $ \text{GCD}(30, 20) = \text{GCD}(20, 30 \% 20) = \text{GCD}(20, 10) $
• $ \text{GCD}(20, 10) = \text{GCD}(10, 20 \% 10) = \text{GCD}(10, 0) $
• $ \text{GCD}(10, 0) = 10 $

因此，GCD(30, 20) = 10。

四、扩展欧几里得算法公式推导

扩展欧几里得算法不仅计算GCD，还能够找到整数 $x$ 和 $y$，使得：
$$ ax + by = \text{GCD}(a, b) $$
这就是贝祖等式（Bézout's identity）。

1. 基础公式

假设有两个整数 $a$ 和 $b$，并且 $a \geq b$。根据欧几里得算法，我们可以写出：
$$ a = bq + r $$
其中，$q$ 是商，$r$ 是余数（即 $0 \leq r < b$）。

根据贝祖等式，有：
$$ \text{GCD}(a, b) = \text{GCD}(b, r) $$

2. 反向求解贝祖系数

假设在某一步计算中：
$$ \text{GCD}(b, r) = bx_1 + ry_1 $$
我们可以写出：
$$ r = a - bq $$
代入上式，得到：
$$ \text{GCD}(a, b) = bx_1 + (a - bq)y_1 $$
展开后可以得到：
$$ \text{GCD}(a, b) = ay_1 + b(x_1 - qy_1) $$

因此，我们得到：
$$ x = y_1 $$
$$ y = x_1 - qy_1 $$

五、Python实现

以下是使用Python实现扩展欧几里得算法的详细代码：

def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    else:
        gcd, x1, y1 = extended_gcd(b, a % b)
        x = y1
        y = x1 - (a // b) * y1
        return gcd, x, y

# 示例使用
a = 30
b = 20
gcd, x, y = extended_gcd(a, b)
print(f"最大公约数（GCD）：{gcd}")
print(f"系数 x 和 y 分别为：{x}, {y}")
print(f"验证贝祖等式：{a}*{x} + {b}*{y} = {gcd}")

代码解析

1. 基本情况：
   如果 $ b = 0 $，则直接返回 $ \text{GCD}(a, b) = a $，并且 $ x = 1 $，$ y = 0 $。
2. 递归计算：
   计算 $ \text{GCD}(b, a \% b) $ 并获得其贝祖系数 $ x1 $ 和 $ y1 $。
3. 反向求解：
   根据公式 $ x = y1 $，$ y = x1 - (a // b) * y1 $ 计算出当前的贝祖系数 $ x $ 和 $ y $。
4. 返回结果：
   最终返回 $ \text{GCD} $ 及其对应的贝祖系数 $ x $ 和 $ y $。

通过上述推导和实现，我们可以有效地求解两个整数的最大公约数及其贝祖系数。