python编程实现欧几里得算法及其拓展算法，计算两个数最大公约数，求指定数的模逆元

欧几里得算法是用于计算两个整数的最大公约数（GCD，Greatest Common Divisor）的古老算法，也是Python中求解这个问题的基础。基本步骤如下：

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

在这个函数中，a 和 b 是两个待求最大公约数的数，通过不断取余并交换数值，直到b为0，此时a即为最大公约数。

拓展到求模逆元（Modular Inverse），即给定两个正整数a和m，找到一个整数x使得ax ≡ 1 (mod m)。可以先通过gcd求出a和m的GCD，然后借助扩展欧几里得算法：

def extended_gcd(a, m):
    if m == 0:
        return a, 1, 0
    d, x, y = extended_gcd(m, a % m)
    return d, y, x - (a // m) * y

def mod_inverse(a, m):
    d, x, _ = extended_gcd(a, m)
    # 如果a和m互质，则存在模逆元
    if d == 1:
        return x % m
    else:
        raise ValueError("a和m不是互质的，无法找到模逆元")

`mod_inverse`函数中，如果返回的d（最大公约数）为1，说明a和m有互逆元素，此时x就是所求的模逆元。若d不等于1，表示a和m不互质，没有模逆元存在，会抛出异常。