扩展欧几里得算法公式推导与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 的余数。
步骤:
- 若 $ b = 0 $,则 $ \text{GCD}(a, b) = a $。
- 否则,令 $ 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}")
代码解析
- 基本情况:
如果 $ b = 0 $,则直接返回 $ \text{GCD}(a, b) = a $,并且 $ x = 1 $,$ y = 0 $。 - 递归计算:
计算 $ \text{GCD}(b, a \% b) $ 并获得其贝祖系数 $ x1 $ 和 $ y1 $。 - 反向求解:
根据公式 $ x = y1 $,$ y = x1 - (a // b) * y1 $ 计算出当前的贝祖系数 $ x $ 和 $ y $。 - 返回结果:
最终返回 $ \text{GCD} $ 及其对应的贝祖系数 $ x $ 和 $ y $。
通过上述推导和实现,我们可以有效地求解两个整数的最大公约数及其贝祖系数。