扩展欧几里得求逆元 - 编程数学 | C++ & Algorithm 编程研习社

扩展欧几里得求逆元：从余数游戏到代码实现

1. 从“一次除法”说起：什么是模逆元？

想象你在玩一个“时钟游戏”。时钟只有0到11这12个数字，超过12就自动减去12。比如，现在是7点，过了6小时是几点？7+6=13，13-12=1，所以是1点。这里的加法、减法都在“模12”的世界里进行。我们把这个环境叫做模数为12的剩余系。

在这个世界里，你想做“除法”。比如，你知道3乘以某个数等于9，问这个数是多少？在普通算术中，答案是9÷3=3。但在模12的世界里，3乘以几等于9呢？3×3=9，正好成立，所以3就是答案。那如果问：3乘以几等于1？也就是说，在模12下，哪个数能和3相乘得到1？3×？≡1 (mod 12)。你可能会想：3×4=12≡0，不是1；3×5=15≡3，不是1……试试3×？=13？不行，因为3×4=12, 3×5=15，差一点。实际上，3在模12下没有逆元，因为3和12不互质（有公因子3），所以不存在整数x使得3x ≡ 1 mod 12。

这个“在模m下，找到一个数x使a×x ≡ 1 (mod m)”的过程，就叫做 求模逆元。x就称为a模m的逆元，记作a⁻¹ (mod m)。逆元存在的条件是：a与m互质（最大公约数为1）。

思考：为什么逆元这么重要？因为有了逆元，我们就能在模运算里做“除法”了！比如要计算 b ÷ a mod m，其实就是b乘以a的逆元。这在密码学、算法竞赛中非常常见。

2. 先复习老朋友：辗转相除法求最大公约数

在正式讲逆元之前，我们先复习一下求两个数最大公约数（GCD）的古老方法——辗转相除法（也叫欧几里得算法）。这个算法像“切蛋糕”一样，每次用大数除以小数，取余数，然后交换位置，一直做到余数为0为止。最后剩下的除数就是最大公约数。

生活中的例子：你有12块巧克力和9颗糖果，要平均分给几个朋友，每个朋友拿到的巧克力数量和糖果数量应该一样多，而且不能有剩余。最多能分给几个朋友？这就是求12和9的最大公约数。12 ÷ 9 = 1 余 3，9 ÷ 3 = 3 余 0，所以最大公约数是3。最多可以分给3个朋友。

代码实现（C++）：

int gcd(int a, int b) {               // 计算 a 和 b 的最大公约数
    while (b != 0) {                   // 当余数不为0时继续
        int temp = b;                  // 保存除数
        b = a % b;                     // 新余数
        a = temp;                      // 原来的除数变成被除数
    }
    return a;                          // 返回最大公约数
}

Python版（更简洁）：

def gcd(a, b):
    while b != 0:
        a, b = b, a % b   # 同时交换：新 a = 原 b，新 b = 原 a % 原 b
    return a

3. 升级版：扩展欧几里得算法——不仅能求gcd，还能求逆元

辗转相除法只能告诉我们两个数是否互质（gcd=1），但如果我们想求逆元，还需要找到那个特殊的“乘数”。扩展欧几里得算法就像一个“侦探”，它不仅告诉我们最大公约数是多少，还能顺藤摸瓜找出满足下面方程的整数解：

a × x + m × y = gcd(a, m)

如果a和m互质，gcd=1，那么等式变成：

a × x + m × y = 1

两边对m取模，m×y ≡ 0 (mod m)，所以得到 a × x ≡ 1 (mod m)。好巧！这个x就是a模m的逆元！

怎么找到x和y？ 算法利用辗转相除法的逆推过程。比如我们想求3模11的逆元（11是质数，3和11互质）。我们手动试一下：3×4=12≡1 mod 11，所以逆元是4。但电脑需要系统的方法。

扩展欧几里得算法的核心思想：在递归中记录每一步的系数。用递归方式更容易理解：

假设我们在辗转相除法的某一步：a = b × q + r（q是商，r是余数），并且我们已经知道对于b和r，存在一组解使得： b × x₁ + r × y₁ = gcd(b, r) = gcd(a, b)

那么代入 r = a - b×q，得到： b × x₁ + (a - b×q) × y₁ = a × y₁ + b × (x₁ - q×y₁) = gcd(a, b)

所以新的一组解是：x = y₁，y = x₁ - q×y₁。

代码实现（C++，递归版）：

#include <iostream>
using namespace std;

// 扩展欧几里得算法：求 ax + by = gcd(a,b) 的一组整数解
// 返回 gcd，同时通过引用返回 x 和 y
int extendedGcd(int a, int b, int &x, int &y) {
    if (b == 0) {               // 递归边界：b=0时，gcd=a
        x = 1;                  // 此时 a×1 + 0×0 = a
        y = 0;
        return a;
    }
    int x1, y1;                 // 用来保存子问题的解
    int g = extendedGcd(b, a % b, x1, y1);  // 递归调用，注意参数交换
    // 回溯：根据子问题的解计算当前解
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

// 利用扩展欧几里得求 a 模 m 的逆元（要求 gcd(a,m)=1）
int modInverse(int a, int m) {
    int x, y;
    int g = extendedGcd(a, m, x, y);
    if (g != 1) {
        return -1;              // 没有逆元，返回-1表示不存在
    } else {
        // 保证结果在 0 到 m-1 之间
        return (x % m + m) % m;
    }
}

int main() {
    int a = 3, m = 11;
    int inv = modInverse(a, m);
    if (inv == -1) {
        cout << a << " 和 " << m << " 不互质，没有逆元" << endl;
    } else {
        cout << a << " 模 " << m << " 的逆元是 " << inv << endl;
        cout << "验证: " << a << " * " << inv << " % " << m << " = " 
             << (a * inv) % m << endl;
    }
    return 0;
}

Python版（同样递归，但更贴近数学表达）：

def extended_gcd(a, b):
    """返回 (gcd, x, y) 使得 a*x + b*y = gcd"""
    if b == 0:
        return (a, 1, 0)
    g, x1, y1 = extended_gcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return (g, x, y)

def mod_inverse(a, m):
    g, x, y = extended_gcd(a, m)
    if g != 1:
        return None  # 没有逆元
    else:
        return x % m  # Python取余自动保证非负？注意：x可能为负，所以用 % m

# 测试
a = 3
m = 11
inv = mod_inverse(a, m)
print(f"{a} 模 {m} 的逆元是 {inv}")
print(f"验证: {a} * {inv} % {m} = {(a * inv) % m}")

4. 常见错误与避坑指南

错误1：不检查互质直接求逆元 有些同学一上来就用扩展欧几里得，拿到结果就用，但忘记检查gcd是否为1。如果a和m不互质，扩展欧几里得求出的x并不是逆元，因为a×x ≡ gcd(a,m) ≠ 1。比如a=3,m=12，求出的x是某个值，但3×x ≡ 3 (mod 12)，不是1。一定要先检查互质！

错误2：逆元是负数怎么办？ 扩展欧几里得求出的x可能是负数，比如求3模11的逆元，算法可能返回-7而不是4（因为3×(-7) = -21 ≡ 1 mod 11）。所以我们要把结果调整到 [0, m-1] 范围内，常见做法是 (x % m + m) % m。

错误3：混淆逆元和分数意义 在普通算术中，3的倒数就是1/3，是个分数。但在模运算里，逆元是整数，比如3模11的逆元是4，因为3×4=12≡1。千万不要把分数概念搬过来！逆元是整数，而且只在模的世界里成立。

错误4：递归太深导致栈溢出 如果m特别大（比如10^9），递归深度可能达到几十万，C++默认栈空间不够。建议把递归版写成迭代版（非递归），或者使用Python的递归时注意限制。对于中小学生竞赛，通常模数不会太大，但了解即可。

5. 完整示例：用逆元计算模除法

假设班级有7个同学要平分8包薯片的积分，每包薯片价值10元，但总分是7人的“模”世界。我们想计算8÷7 mod 10，其实就是8乘以7模10的逆元。因为7和10互质吗？7和10的gcd=1，所以有逆元。用扩展欧几里得求7模10的逆元：7×3=21≡1 mod 10，所以逆元是3。8×3=24≡4 mod 10。所以8÷7在模10下等于4。

完整可运行代码（C++，已包含上面所有函数）：

#include <iostream>
using namespace std;

// 扩展欧几里得
int extendedGcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1; y = 0;
        return a;
    }
    int x1, y1;
    int g = extendedGcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

// 求逆元，返回-1表示不存在
int modInverse(int a, int m) {
    int x, y;
    int g = extendedGcd(a, m, x, y);
    if (g != 1) return -1;
    return (x % m + m) % m;
}

int main() {
    int a = 7, m = 10;
    int inv = modInverse(a, m);
    if (inv == -1) {
        cout << a << " 和 " << m << " 不互质，没有逆元" << endl;
    } else {
        cout << "7 模 10 的逆元是 " << inv << endl;
        // 计算 8 ÷ 7 mod 10
        int dividend = 8;
        int quotient = (dividend * inv) % m; // 除以 a 等于乘以逆元
        cout << "8 ÷ 7 mod 10 = " << quotient << endl;
    }
    return 0;
}

输出：

7 模 10 的逆元是 3
8 ÷ 7 mod 10 = 4

6. 延伸：还有其他求逆元的方法吗？

扩展欧几里得是求逆元的通用方法，适合任何模数（只要互质）。但如果模数m是质数（比如常用的质数1000000007），还有更简单的费马小定理：a^(m-2) ≡ a⁻¹ (mod m)。直接用快速幂计算a的m-2次幂即可，代码更短。不过费马小定理要求m是质数，而扩展欧几里得没有这个限制。

另外，如果要求多个数的逆元，可以用线性递推，但那是进阶内容了。

相关知识点：

辗转相除法（欧几里得算法）
拓展欧几里得算法（用来解不定方程ax+by=c）
费马小定理
线性同余方程（如 ax ≡ b (mod m) 的解法）
快速幂

掌握了扩展欧几里得求逆元，你就拥有了在模世界里自由做“除法”的能力。以后遇到分数取模、RSA加密、同余方程求解，都能从容应对。