用Pyrhon编写扩展欧几里得算法

在Python中，我们可以使用递归的方式来实现扩展欧几里得算法，也称为中国剩余定理（Chinese Remainder Theorem，CRT）的逆元部分。扩展欧几里得算法不仅能够求解两个整数的最大公约数（GCD），还能找到它们相对应的贝祖等式解，即存在整数x和y使得ax + by = gcd(a, b)。

下面是一个简单的Python函数实现：

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

# 使用示例
def find_inverse_modulo(n, mod):
    _, inv, _ = extended_euclidean_algorithm(n, mod)
    return inv % mod  # 返回n对于mod的逆元

# 测试
a = 7
b = 4
gcd, x, y = extended_euclidean_algorithm(a, b)
inverse_a = find_inverse_modulo(a, b)
print(f"GCD of {a} and {b}: {gcd}")
print(f"Inverse of {a} modulo {b}: {inverse_a}")

在这个例子中，`find_inverse_modulo` 函数用于计算给定模值 `mod` 下 `a` 的逆元。