拓展欧几里得 python实现 寻找数a关于26的乘法逆元

拓展欧几里得算法是一种求解两个整数的最大公约数（GCD）以及其中一个数除以另一个数的逆元的方法。在Python中，你可以使用这个算法找到一个数a关于模m（这里是26）的乘法逆元，即满足 `a * inv % m == 1` 的inv。下面是一个简单的实现：

def extended_euclidean_algorithm(a, m):
    """
    使用扩展欧几里得算法计算 a 关于模 m 的逆元
    """
    # 初始化变量
    x, y, prev_x, prev_y = 0, 1, 1, 0

    while a != 0:
        q, r = divmod(m, a)
        m, a, x, y = a, r, prev_y, x - q * prev_y

    # 如果r == 1，则x就是a的逆元 mod m
    return x if r == 1 else None

# 示例：寻找7关于模26的逆元
a = 7
m = 26
inverse_of_a_mod_m = extended_euclidean_algorithm(a, m)

if inverse_of_a_mod_m is not None:
    print(f"7关于模26的乘法逆元是: {inverse_of_a_mod_m}")
else:
    print("找不到逆元，因为a和m可能互质")