用python实现二进制扩展欧几里得算法

下面是用 Python 实现二进制扩展欧几里得算法的代码：

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

在这个函数中，我们使用递归来计算最大公约数和乘法逆元。当 b 等于 0 时，a 就是最大公约数，x 等于 1，y 等于 0。否则，我们递归地调用函数，直到 b 等于 0。然后，我们使用递归返回的结果来计算 x 和 y。

接下来，我们可以使用这个函数来计算两个数 a 和 b 的最大公约数和它们的乘法逆元：

a = 21
b = 14

gcd, x, y = binary_extended_gcd(a, b)

print("gcd({0}, {1}) = {2}".format(a, b, gcd))
print("{0} * {1} + {2} * {3} = {4}".format(a, x, b, y, gcd))

输出结果为：

gcd(21, 14) = 7
21 * 1 + 14 * -1 = 7

这表明 21 和 14 的最大公约数为 7，21 和 14 的乘法逆元为 -1（在模 14 意义下）。