理解扩展Euclid算法的求gcd(a(x),b(x))和多项式乘法逆元的原理； 2.通过编程实现Euclid_ex算法。python语言实现

扩展欧几里得算法（Extended Euclidean Algorithm），也称为中国剩余定理（Chinese Remainder Theorem）的一种变形，用于同时计算两个或更多整数的最大公约数以及它们对应系数的逆元。这个算法不仅能找到常规欧几里得算法中的gcd(a, b)，还能找到使得a * x + b * y = gcd(a, b)成立的x和y值。

多项式乘法的逆元涉及模逆运算，即寻找一个整数c，使得c mod a = 1，这里的a是需要找逆元的系数。对于多项式gcd(a(x), b(x))，如果它们不是线性的，我们通常会将其转化为线性形式，然后利用扩展欧几里得算法的原理来找到逆元。

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

def extended_gcd(a, b):
    # 辅助函数，用于递归实现扩展欧几里德算法
    def egcd(a, b):
        if a == 0:
            return (b, 0, 1)
        else:
            g, y, x = egcd(b % a, a)
            return (g, x - (b // a) * y, y)

    _, x, _ = egcd(a, b)
    return x % b  # 返回x的值，它是a除以b的逆元

# 示例
a = 35  # 要查找逆元的系数
b = 14  # 另一个系数
inv_a_mod_b = extended_gcd(a, b)
print(f"模{b}下，a={a}的逆元是：{inv_a_mod_b}")

# 对于多项式gcd(a(x), b(x))，假设a(x)=ax+b, b(x)=cx+d，则逆元将用于计算c*x+(-d)*inv_a_mod_b