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

欧几里得算法（Euclidean Algorithm），也叫辗转相除法，用于计算两个整数的最大公约数（Greatest Common Divisor，GCD）。其基本思想是：若a和b是两个正整数，其中a大于b，则它们的最大公约数等于b和两数相除余数a mod b的最大公约数。

以下是Python版的欧几里得算法实现：

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

扩展算法可以找到两个数a和b（假设a > b）的最小公倍数（Least Common Multiple，LCM），公式为 LCM(a, b) = |a * b| / GCD(a, b)。

至于计算模逆元（Modular Inverse），它是在数学领域的一个概念，当寻找一个整数x对于给定的模m，满足 x * y ≡ 1 (mod m)，我们就称y为x关于模m的逆元。在编程中，我们通常使用扩展欧几里得算法（Extended Euclidean Algorithm）来同时找到gcd和模逆元，例如在RSA加密中应用。

下面是Python版的扩展欧几里得算法：

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

def modular_inverse(a, m):
    _, inv, _ = extended_gcd(a, m)
    if inv < 0:
        inv += m
    return inv