扩展欧几里得算法python

扩展欧几里得算法（Extended Euclidean Algorithm）也被称为扩展欧几里得定理，用于计算两个整数 a 和 b 的最大公约数（GCD）以及它们的贝祖等式的系数 x 和 y，满足以下等式：

ax + by = gcd(a, b)

以下是一个用 Python 实现的扩展欧几里得算法：

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

这个函数接受两个整数 a 和 b 作为输入，返回它们的最大公约数 gcd 以及 x 和 y 的值，它们满足贝祖等式。如果 a 是 0，那么 gcd 等于 b，此时 x 等于 0，y 等于 1。否则，递归调用函数，计算 b 对 a 取模的结果和 a 之间的 GCD，同时计算 x 和 y 的值。

下面是一个示例，演示如何使用扩展欧几里得算法来计算 35 和 15 的最大公约数以及它们的贝祖等式的系数：

gcd, x, y = extended_euclidean_algorithm(35, 15)
print("gcd(35, 15) = {}".format(gcd))
print("x = {}, y = {}".format(x, y))

输出：

gcd(35, 15) = 5
x = 1, y = -2

因此，35 和 15 的最大公约数是 5，它们的贝祖等式为 1 x 35 + (-2) x 15 = 5。