扩展的欧几里得算法求逆元

扩展的欧几里得算法是一种求解两个整数的最大公约数的算法，同时可以求出这两个整数的一组贝祖恒等式解，从而求出其中一个整数关于模意义下另一个整数的乘法逆元。

设要求的两个整数为a和b，它们的最大公约数为gcd(a, b)，则有以下的扩展欧几里得算法：

1. 初始化：令r0 = a, r1 = b, x0 = 1, x1 = 0, y0 = 0, y1 = 1。

2. 迭代计算：对于i = 1, 2, ...，执行以下步骤：

a. 计算商和余数：qi = ri-2 // ri-1，ri = ri-2 % ri-1。

b. 更新解向量：xi = xi-2 - qi * xi-1，yi = yi-2 - qi * yi-1。

c. 判断终止条件：若ri-1 = 0，则算法结束，此时gcd(a, b) = ri，同时x1和y1即为一组贝祖恒等式解。

3. 求逆元：若gcd(a, b) = 1，则a关于模意义下b的乘法逆元为x1 % b（注意要确保x1为正整数）。

下面是一个Python实现的扩展欧几里得算法：

def extended_gcd(a, b):
    r0, r1, x0, x1, y0, y1 = a, b, 1, 0, 0, 1
    while r1 != 0:
        q = r0 // r1
        r0, r1 = r1, r0 % r1
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return r0, x0, y0

def mod_inverse(a, b):
    gcd, x, y = extended_gcd(a, b)
    if gcd != 1:
        raise ValueError('No inverse exists')
    else:
        return x % b

我们可以使用这个函数来求出任意一个数在模意义下的乘法逆元，比如：

>>> mod_inverse(7, 11)
8
>>> mod_inverse(3, 5)
2
>>> mod_inverse(4, 8)
None

需要注意的是，如果要求解的两个数a和b不互质，则它们的乘法逆元不存在。在上面的代码中，如果gcd不等于1，则会抛出一个异常来提示这种情况。