模逆元（数论倒数）的三种求法与代码实现

写代码或者刷算法题的时候，如果连续碰到“模一个素数”和“算一个分数”，你大概率会被同一个东西卡住——逆元，也叫数论倒数。比如要算 5 ÷ 3 mod 7，你对着整数除法想半天也得不到一个“正常”答案，因为在模 7 的世界里，除法根本没有被定义。逆元解决的就是这个问题：把除法转换成乘法，找一个数 x，让 3 乘以 x 之后在模 7 意义下等于 1。找到这个 x，5 ÷ 3 就能变成 5 乘 x。

就这么一个概念，在数论、算法竞赛、密码学的 RSA 里反复出现。这篇文章作为系列 P1，我打算从零开始，把逆元是什么、怎么求、代码怎么写、新手容易踩哪些坑一次性讲透。适合刚接触数论的竞赛选手、对密码学感兴趣的程序员，以及准备复试被数论问到的同学。今天讲的都是最基础也最核心的东西，理解透了，后面看原根、离散对数、二次剩余都会轻松很多。

1. 数论倒数到底在算什么

1.1 除法在模世界被卡住了

先弄明白一件事：模运算里，加法、减法、乘法都很自然。7 小时转一圈的钟表上，3 点加 5 小时是 1 点，这本质上就是 (3 + 5) mod 7 = 1。乘法呢，可以理解成多次加法，比如 3 × 3 = 9，在模 7 下等于 2，也没毛病。可一旦碰到除法，问题就来了：5 ÷ 3 在模 7 下等于多少？

你要是直接做 5 ÷ 3，得到的是 1.666...，这是个小数，而模 7 的世界里只有 0 到 6 这 7 个整数。就算你把 5 ÷ 3 想成“哪个整数乘以 3 之后等于 5”，2 × 3 = 6，1 × 3 = 3，试一圈也找不到一个整数能让它模 7 等于 5。

换一种思路：在实数里，除法其实就是乘以这个数的倒数，3 的倒数是 1/3，因为 3 × (1/3) = 1。那么在模 7 的世界里，能不能也找一个“倒数”呢？也就是说，找一个小整数 x，使 3 × x ≡ 1 (mod 7)。你挨个试：3 × 1 = 3，3 × 2 = 6，3 × 3 = 9 ≡ 2，3 × 4 = 12 ≡ 5，3 × 5 = 15 ≡ 1。找到了，x = 5。

这个 5，就是 3 在模 7 意义下的“倒数”，也叫乘法逆元。有了它，5 ÷ 3 就能写成 5 × 5 = 25，模 7 等于 4。你验证一下：4 × 3 = 12 ≡ 5，完全正确。所以逆元的本质，就是用乘法去模拟除法，让原本没法直接算的“模除法”变得可算。

1.2 定义与存在条件：不是所有数都有“钥匙”

正式一点，如果 ax ≡ 1 (mod m)，就把 x 称为 a 在模 m 意义下的乘法逆元，记作 a⁻¹。注意这个记号不是实数里的倒数，但在模意义下它的行为和倒数一模一样：a 乘以 a⁻¹ 的结果，在模 m 下等于单位元 1。

既然跟倒数这么像，那第一个要搞清楚的问题就是：是不是随便一个数都有逆元？答案是：不一定。逆元存在的充要条件是 gcd(a, m) = 1，也就是 a 和模数 m 互质。

为什么？把 ax ≡ 1 (mod m) 展开，等价于存在整数 k，使得 ax - km = 1。如果 gcd(a, m) = d > 1，那么 d 一定整除 ax，也一定整除 km，所以 d 必须整除 1，这显然不可能。反过来，如果 gcd(a, m) = 1，根据后面要讲的扩展欧几里得定理，一定存在整数 x、k 满足 ax - km = 1，也就是逆元一定存在。所以“有没有逆元”这个问题，本质上是“互不互质”的问题。

这里有个很重要的推论：当模数 m 是素数时，1 到 m-1 之间所有整数都和 m 互质，也就是说除了 0 和 m 的倍数之外，每个数都有逆元。这就是为什么后面大量数论题目默认模数是 1000000007 这种大素数，题目敢让你随便做除法，就是因为每个非零数的逆元都存在。而一旦模数是合数，比如模 4 之下，2 就没有逆元，你试遍 0、1、2、3，2 乘以任何数模 4 都只能是 0 或 2，永远得不到 1。

2. 求逆元的三种主流方法

2.1 扩展欧几里得：最通用的解法

求逆元的第一个方法，也是适用范围最广的方法，叫扩展欧几里得算法，简称 exgcd。大家都学过辗转相除法求 gcd，它基于一个恒等式：gcd(a, b) = gcd(b, a mod b)，一直递归到 b = 0 时，gcd 就是 a。

扩展欧几里得在此基础上多算了一样东西：它不光求出 gcd(a, b)，还能同时找出一组整数 x、y，使得 ax + by = gcd(a, b)。这个式子叫裴蜀定理，意思是说两个数的最大公约数一定能写成这两个数的整数线性组合。

把 b 换成 m，如果 gcd(a, m) = 1，那 exgcd 返回的就是 ax + my = 1。把这个式子两边同时模 m，my 这一项直接消失，剩下 ax ≡ 1 (mod m)，所以 exgcd 返回的 x 就是逆元。

举一个具体的例子：求 3 在模 7 下的逆元。手动跑一遍：

7 = 2 × 3 + 1 1 = 7 - 2 × 3

把第二个式子写成 3 × (-2) + 7 × 1 = 1，所以 x = -2。但模 7 意义下，-2 ≡ 5，所以逆元是 5，和前面试出来的结果一致。

这里要注意：exgcd 算出来的 x 可能是负数，这时候一定要“修正”到 [0, m-1] 区间。方法就是 x = (x % m + m) % m，先取模再加模再取模，保证结果非负。

exgcd 的复杂度是 O(log min(a, m))，非常快。它的最大优势是模数不要求是素数，只要互质就行，所以它是处理合数模场景的底牌。

2.2 费马小定理：模素数的快速通道

如果你确定模数 p 是素数，那还有一条更快的路：费马小定理。定理说，对于素数 p，且 gcd(a, p) = 1，有 a^(p-1) ≡ 1 (mod p)。

这个式子可以变形：a × a^(p-2) ≡ 1 (mod p)，所以 a 的逆元就是 a^(p-2) mod p。只要用快速幂把 a^(p-2) 算出来，逆元就拿到了。

为什么费马小定理成立？我给出一个直观的证明思路。考虑 a、2a、3a、...、(p-1)a 这 p-1 个数模 p 的结果。因为 gcd(a, p) = 1，每个数都不是 p 的倍数，而且任意两个的差也不能被 p 整除，所以它们模 p 后恰好是 1 到 p-1 的一个排列。把它们全部乘起来，就有 a^(p-1) × (p-1)! ≡ (p-1)! (mod p)，两边消去 (p-1)!，就得到 a^(p-1) ≡ 1 (mod p)。

这个方法在竞赛里用得最多，原因很现实：题目经常给你一个大素数模数，比如 1e9+7、998244353，这时候求逆元就是一行快速幂的事。需要注意的是，费马小定理的前提是“p 是素数”，只要模数是合数，a^(m-2) 很可能不是逆元，这一点后面专门讲坑。

2.3 欧拉定理：把素数的限制放宽

费马小定理虽然好用，但素数这个前提太苛刻了。如果模数是合数，有没有一个更一般的定理？有，就是欧拉定理。欧拉定理说：如果 gcd(a, m) = 1，那么 a^φ(m) ≡ 1 (mod m)，其中 φ(m) 是欧拉函数，表示 1 到 m 之间与 m 互质的整数个数。

根据欧拉定理，a 的逆元就是 a^(φ(m)-1) mod m。当 m 是素数 p 时，φ(p) = p-1，欧拉定理就退化成费马小定理，所以费马小定理其实是欧拉定理的特例。

用欧拉定理求逆元的关键是算出 φ(m)。如果 m 不大，可以暴力枚举统计互质数；如果 m 很大，一般要先分解质因数，再运用公式 φ(m) = m × ∏(1 - 1/p_i) 计算。每多一个质因子，就乘上一个 (p-1)/p。这个公式在初等数论里很常用，但本文 P1 阶段先不展开，知道有这么一条通用路线即可。

三种方法做个简单选型：模数是素数，优先费马小定理；模数是合数但互质，用扩展欧几里得最省事，或者用欧拉定理；而且 exgcd 还能用来判断逆元是否存在，这个别名“万能底牌”不是白叫的。

3. 直接能用的代码模板

3.1 扩展欧几里得模板

先上 C++ 的 exgcd 模板。代码很短，但递归边界、引用传参这两点要记牢。

#include <bits/stdc++.h> using namespace std; long long exgcd(long long a, long long b, long long& x, long long& y) { if (b == 0) { x = 1; y = 0; return a; } long long g = exgcd(b, a % b, y, x); y -= (a / b) * x; return g; } // 求 a 在模 m 下的逆元，若不存在返回 -1 long long inv(long long a, long long m) { long long x, y; long long g = exgcd(a, m, x, y); if (g != 1) return -1; return (x % m + m) % m; }

递归到 b = 0 的时候，gcd 是 a，此时显然 a × 1 + 0 × 0 = a，所以 x = 1，y = 0。回溯的过程稍微有点绕，关键是利用下一层的 x、y 来更新当前层的值。模板里直接递归时交换 x、y 的位置，再修正 y，这是最常见的写法，我建议直接背熟。

C++ 里要注意，a、m 都可能达到 1e9 量级，中途乘法可能溢出 int，所以要用 long long。最后的(x % m + m) % m这一步是必须的，它能保证返回的是非负且小于 m 的逆元。

Python 版更符合直觉，直接同步返回 gcd 和一组解：

def exgcd(a, b): if b == 0: return a, 1, 0 g, x1, y1 = exgcd(b, a % b) return g, y1, x1 - (a // b) * y1 def inv(a, m): g, x, _ = exgcd(a, m) if g != 1: return -1 return (x % m + m) % m

用法验证：inv(3, 7)返回 5，inv(2, 4)返回 -1。这一份模板可以直接拿到平时的模运算场景里用。

3.2 费马小定理 + 快速幂模板

当模数 p 是大素数时，逆元 = a^(p-2) mod p，核心就是快速幂。

long long qpow(long long a, long long b, long long mod) { long long res = 1; while (b > 0) { if (b & 1) res = res * a % mod; a = a * a % mod; b >>= 1; } return res; } // 调用方式，p 必须是素数 long long inv_prime_mod(long long a, long long p) { return qpow(a, p - 2, p); }

Python 更简单，内置pow第三个参数就是模数，内部已经是快速幂实现：

def inv_prime_mod(a, p): return pow(a, p - 2, p)

有个细节提醒一下：C++ 里的pow是浮点函数，千万别和快速幂混淆，我见过不少新手拿pow(a, p-2)去取模，结果得到一个完全没有意义的大浮点数，然后对着答案怀疑人生。写求逆元的代码，老老实实用整型快速幂或者 Python 内置的三参 pow。

3.3 从 1 连算到 n 的线性递推求逆元

有时候题目要一次性算很多个数的逆元，比如预处理 1!、2!、...、n! 的逆元。如果对每个数都跑一次 exgcd 或快速幂，复杂度是 O(n log mod)，数据一大就容易超时。这时候有个 O(n) 的线性递推公式，前提同样是模数 p 为素数。

公式是：

inv[i] = -(p // i) * inv[p % i] % p

写成防负数的代码就是：

vector<long long> inv_all(int n, long long p) { vector<long long> inv(n + 1); inv[1] = 1; for (int i = 2; i <= n; i++) { inv[i] = (p - p / i) * inv[p % i] % p; } return inv; }

这个公式怎么来的？设 p = (p // i) * i + (p % i)，两边在模 p 下看，就有 p % i ≡ -(p // i) * i (mod p)。两边同时乘以 inv[p % i] × inv[i]，得到 inv[i] ≡ -(p // i) * inv[p % i] (mod p)。把负号处理掉，就是上面的写法。

用 p = 7 验证一下：inv[1] = 1，inv[2] = (7 - 3) × inv[1] % 7 = 4，inv[3] = (7 - 2) × inv[1] % 7 = 5，inv[4] = (7 - 1) × inv[3] % 7 = 6 × 5 % 7 = 2。你检查：2 × 4 = 8 ≡ 1，3 × 5 = 15 ≡ 1，4 × 2 = 8 ≡ 1，全部正确。有了这个数组，后面算组合数取模就非常舒服。

4. 实战里逆元的价值

4.1 模意义下的分数与除法

很多人第一次真正需要逆元，是在做概率 DP、期望、递推这类题的时候。比如递推公式是 f[i] = f[i-1] / k + something，所有结果都要对一个素数模取模。这时候你没法真的做小数除法，因为取模只对整数有意义。

正确做法是把“除以 k”换成“乘以 k 的逆元”。换句话说，模意义下分数 a/b 定义为 a × b⁻¹ mod m。只要 b 和模数互质，这个分数就有明确的整数取值。

举个例子：在模 7 下计算 5 / 2。inv(2, 7) = 4，所以 5 / 2 mod 7 = 5 × 4 = 20 ≡ 6。你验证：6 × 2 = 12 ≡ 5，完全正确。这个 6 在模 7 的世界里，就扮演着“二分之五”的角色。这种操作在普通算术里看起来很奇怪，但在模世界里是自洽的。

4.2 组合数取模的经典套路

再往实战走一步，组合数取模大概是逆元出场率最高的地方。C(n, k) = n! / (k! × (n-k)!)，这里面有除法，所以模素数 p 下不能直接算。但是只要预处理阶乘和阶乘的逆元，组合数计算就变成了几次乘法。

具体套路分三步：

1. 预处理 fac[i]，从 0 循环到 n，fac[0] = 1，fac[i] = fac[i-1] × i % p。
2. 用费马小定理算 fac[n] 的逆元，然后反向递推得到所有阶乘逆元：invfac[n] = qpow(fac[n], p-2, p)，invfac[i-1] = invfac[i] × i % p。
3. 组合数 C(n, k) = fac[n] × invfac[k] × invfac[n-k] % p。

这个套路几乎是组合计数题的标配，你能在无数题解里看到它。为什么需要反向递推而不是单独算每个阶乘逆元？因为单个算是 O(n log p)，反向递推只用一次快速幂，总体 O(n)，这在 n 到 1e6、1e7 的场景下区别很大。如果题目要求多个查询，这个预处理的优势更明显。

当 n、k 超过模数 p 时，上面这个直接算的方法就不对了，要用 Lucas 定理，那是后面章节的内容，但在 P1 阶段先把基础套路练熟。

4.3 密码学里的一个小轮子

逆元不是竞赛专属技巧，它是密码学的地基。最典型的例子就是 RSA 算法里计算私钥 d 的过程。

在 RSA 里，选取两个大素数 p、q，n = p × q，φ(n) = (p-1)(q-1)。然后选一个加密指数 e，使得 gcd(e, φ(n)) = 1。解密指数 d 必须满足 ed ≡ 1 (mod φ(n))。这个 d 就是 e 在模 φ(n) 下的逆元，求解方法正是扩展欧几里得算法。可以说，没有模逆元，RSA 的密钥生成逻辑就崩了。

另外在一些哈希函数、伪随机数生成器、有限域运算的设计里，也会用到模逆元来构造可逆映射。因为逆元保证“乘以一个数再乘以它的逆元”，最后能回到原来的数，这种可逆性在设计双向一致性的计算中非常宝贵。对初学者来说，知道“逆元是密码学的基础零件之一”就够了，真正深入可以在密码学课程里继续展开。

5. 新手翻车现场：常见问题与排查

5.1 逆元不存在时的判断和替代方案

最常遇到的翻车场景，是模数是合数，某个数根本没有逆元。典型例子：求 2 在模 4 下的逆元，你会发现 2 × 0 = 0，2 × 1 = 2，2 × 2 = 0，2 × 3 = 2，永远得不到 1，所以无解。

用 exgcd 求逆元时，返回的 gcd 不是 1 就说明无解，这一点写完模板之后一定别丢。那无解怎么办？看题目是否允许换一种方式，比如把整条递推式稍微化简，或者换一个大素数模数。如果题目设计没问题，逆元一般都会被保证存在，但作为写代码的人，防御性检查很有必要，不要一上来就除。

5.2 负数取模的语言差异

exgcd 返回的 x 经常是负数，比如求 3 模 7 的逆元，原始 exgcd 给出 x = -2。如果不修正，在 C++ 里直接 return -2，你拿着去算 5 × (-2) mod 7，结果可能变成 -3，虽然 (5 × (-2)) mod 7 在数学上等价于 4，但取模运算在 C++ 里对负数的结果也是负数，很容易出锅。

Python 倒是不一样，负数取模会返回非负结果，-2 % 7 等于 5，所以习惯 Python 的选手可能不会意识到这个问题，一旦切到 C++ 就容易栽。统一的处理方法是 (x % m + m) % m，把可能为负的 x 调到 [0, m-1] 区间。这个修正对任何语言都适用，建议封装进 inv 函数里。

5.3 乘法溢出与超大模数的处理

当模数 p 是 1e9+7，int 最多到大概 21 亿，p × p 已经超过 int 上限，所以代码里 a × a % mod 这行，a 和 a 相乘可能直接溢出变成负数。C++ 里解决办法是全部用 long long 存中间变量。

当 p 本身达到 1e18 级别，long long 相乘也会溢出，这时候就要用更高级的手段，比如基于二进制分解的快速乘，或者直接用__int128临时存中间结果。竞赛里一般用不上，但一旦遇到，知道有这么回事就能少走弯路。

5.4 费马小定理的误用场景

把 a^(m-2) mod m 当逆元用，前提是 m 为素数。如果 m 是合数，费马小定理不成立，结果基本是错的。我见过有人用 m = 15，a = 2 去测，直接得出一个“看起来像模运算的数”，结果完全对不上，然后开始怀疑自己代码写错了。

实际处理时，先确认题目里的模数是不是素数。如果是类似 1e9+7、998244353 这类，基本可以确定是素数，放心用费马小定理。如果不是，就用 exgcd 判断并求逆元，千万不要把一个合数当成素数开 floyd 式骚操作。

下面把几个常见问题整理成表：

最后再分享一个我自己的小经验。我当年学逆元，是在做一道概率 DP 题卡了整整一下午，后来把 exgcd 模板在手推纸上跑了好几遍，才真正理解为什么 exgcd 返回的 x 取模之后就是逆元。所以我也建议你，别光背板子，拿笔把“3 在模 7 下的逆元”那一套正向、回溯的过程写一遍，比看十篇博客都管用。下一篇我准备接着讲同余方程、中国剩余定理，或者从逆元延伸出去的原根和离散对数，如果你有更感兴趣的方向，也可以留言告诉我。