扩展欧几里得定理代码实现

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

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

函数 `extended_euclidean_algorithm` 接受两个参数 `a` 和 `b`，并返回三个值：两数的最大公约数 `gcd`，以及 `a` 和 `b` 的贝祖等式中的未知数 `x` 和 `y`。

在函数中，我们首先处理递归基：当 `b` 等于 0 时，`a` 就是最大公约数，`x` 为 1，`y` 为 0。否则，我们递归调用函数，用 `b` 和 `a % b` 代替原来的 `a` 和 `b`，并获取递归调用返回的值 `gcd`、`x1` 和 `y1`。

接下来，我们根据贝祖等式计算 `x` 和 `y`，然后返回 `gcd`、`x` 和 `y`。

下面是一个示例：

a = 15
b = 35
gcd, x, y = extended_euclidean_algorithm(a, b)
print(f"The GCD of {a} and {b} is {gcd}")
print(f"Values of x and y in {a}*x + {b}*y = gcd are {x} and {y}")

输出：

The GCD of 15 and 35 is 5
Values of x and y in 15*x + 35*y = gcd are -2 and 1

这意味着，15 和 35 的最大公约数为 5，且满足贝祖等式：-2*15 + 1*35 = 5。