数论计算必吃榜之『模数乘法逆元』

有模数的乘法逆元是数论计算中的一个基本概念。在日常生活与科学计算中，我们早已习惯了实数域（(mathbb{R})）里“倒数”这一直观概念：给定一个非零实数 (a)，总能找到唯一的数 (a^{-1})，使得

[a times a^{-1} = 1. ]

二的乘法逆元是二分之一，九的乘法逆元是九分之一。“对称”的倒数符合我们的直觉。

现在我们将目光转向离散的模数世界——也就是在某个正整数 (m) 下考察整数的运算时，情况便多了几分趣味与挑战。此时的“模 (m)”把大大小小的整数都“折叠”进 ({0,1,dots,m-1}) 之中，相加相乘后再取余，使数尽其用而不溢出。此时：若对某个整数 (a) 存在 (b)，使得

[a times b equiv 1 pmod m, ]

那么 (b) 就是 (a) 在『模 (m) 』下的『乘法逆元』（乘法可以交换，当然 (a) 也是 (b) 的逆元）。

场景	元素集合	乘法单位	逆元定义
(mathbb R)	所有实数	(1)	对 (aneq0)，都存在唯一 (a^{-1}inmathbb R)，使 (a a^{-1}=1)。
(mathbb Z)	所有整数	(1)	仅 (pm1) 有逆元（是自身）。
整数模环	({0,dots,m-1})	(1pmod m)	若存在 (b) 使 (abequiv1pmod m)，则 (b) 是 (a) 的乘法逆元。（本文主题）

乘法逆元的基本知识

逆元的存在和唯一性

在有限模数的圆环里，“乘法逆元”是否存在呢？大概是怎么样？

质数模数，人人可逆。当模数是质数 (p) 时，(mathbb Z/pmathbb Z) 恰好形成一个有限域。除了 (0)，每个元素都与 (p) 互质，此时每一个元素都存在唯一逆元。

• 存在性：有许多证明方式。可通过后文逆元的求解来理解。
• 唯一性：假设 (abequiv acequiv1pmod p)，则 (pmid a(b-c))。因 (pnmid a)，故 (pmid(b-c)Rightarrow bequiv c)。

此时我们发现，除了 (0) 没有逆元，剩下的所有数都存在逆元，并且要么就是自身( (1) 和 (p-1))，要么两两成对（其他）。

[begin{array}{c|cccccccccc} a & 1 & color{red}{2} & color{green}{3} & color{green}{4} & color{blue}{5} & color{red}{6} & color{gold}{7} & color{gold}{8} & color{blue}{9} & 10 \ hline a^{-1}!bmod 11 & 1 & color{red}{6} & color{green}{4} & color{green}{3} & color{blue}{9} & color{red}{2} & color{gold}{8} & color{gold}{7} & color{blue}{5} & 10 end{array} ]

质数模数带来的普适可逆性，使其成为密码学与竞赛算法的主战场，是我们主要的讨论对象。

合数模数，互质才配拥有“镜像”。若 (m) 为合数，“有逆元”不再是天生权利，而是需通过互质性考核：

[text{存在逆元 }Leftrightarrow gcd(a,m)=1. ]

• 必要性：若 (abequiv1pmod m)，则 (mmid ab-1)。若 (d=gcd(a,m)>1)，则 (dmid (ab-1)) 与 (dmid ab)，从而 (dmid1)，矛盾。
• 充分性：互质时，可和质数模数一样求解。如由扩展欧几里得算法。

[begin{array}{c|ccccccccccccc} a & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \ hline a^{-1}!bmod 14 & 1 & - & 5 & - & 3 & - & - & - & 5 & - & 11 & - & 13 end{array} ]

零元素永远没有逆元，因为 (0times bequiv0neq1)。后文就忽略掉它了。

乘性（积性）

对任意两数 (a,b) 与模 (m)，若均与 (m) 互质，则

[(ab)^{-1}equiv a^{-1},b^{-1}pmod m. ]

证明，直接验证：

[(ab)left(a^{-1}b^{-1}right)equiv (aa^{-1})(bb^{-1})equiv 1pmod m, ]

且唯一性保证这就是 ((ab)^{-1})。这就是“乘积的逆元等于逆元的乘积”。

启示

• 批量计算时可将“大块”拆为小块求逆，再相乘。
• 在算法分析里，可把分数连乘化简为“所有分子相乘 × 所有分母逆元相乘”，大大减轻运算量。

其他性质

逆元的逆元（显然）

[left(a^{-1}right)^{-1}equiv apmod m. ]

消去律
若 (gcd(a,m)=1)，则“乘 (a)”在模 (m) 上是一个双射，可自由左右“消去”：

[abequiv acpmod mquadLongrightarrowquad bequiv cpmod m. ]

这使得线性同余方程

[axequiv bpmod m ]

可直接解为

[x equiv a^{-1} b pmod m, ]

有了这么多优秀性质，乘法逆元真的就像我们的除法分数一样，在整数域运算，却简洁如在实数域中除以 (a)。

乘法单位群的群律视角

记

[U_m=(mathbb Z/mmathbb Z)^times. ]

则 ((U_m,,times)) 满足封闭性、结合律、单位元 1、逆元存在，构成一个有限群。若 (m) 为质数，(U_m) 甚至是循环群。

求解一个数的乘法逆元

在实际应用中，求逆元总不可能一个一个枚举，我们需要利用数学性质高效地“开出”逆元。

扩展欧几里得算法（Extended Euclid）

只需 (gcd(a,m)=1)（不要求 (m) 为素数）。

由于满足互质条件，用扩展欧几里得求出整数解 ((x,y)) 使

[ ax + my = 1. ]

我们发现，按照定义来说则 (x) 就是 (a) 的一个逆元模 (m)，取其最小非负剩余：

[ a^{-1} equiv x bmod m. ]

function ext_gcd(a, b):     if b == 0: return (1, 0, a)     (x1, y1, g) = ext_gcd(b, a mod b)     x = y1     y = x1 - ⌊a/b⌋ * y1     return (x, y, g)  // 主流程 (x, y, g) = ext_gcd(a, m) if g != 1: no inverse inv = (x mod m + m) mod m // 确保取最小的非负剩余。而非得到负数 

时间复杂度 (O(log m))（欧几里得算法的复杂度），因每次递归将参数规模至少减半。通用、稳定，适合任意大整数与合数模数场景。

费马小定理与欧拉定理乘方法

如果模数是质数 (p)，那么由费马小定理 $a^{p-1}equiv 1pmod p $ 可以得出：

[ a^{-1}equiv a^{p-2}pmod p. ]

我们直接计算这个幂就可以得到答案。

如果模数不保证是质数，更一般的欧拉定理 $a^{varphi(m)}equiv 1pmod p $ 可以得出：

[ a^{-1}equiv a^{varphi(m)-1}pmod m, ]

其中 (varphi(m)) 为欧拉函数。这样仅要求 (gcd(a,m)=1)。

使用快速幂求解幂次，复杂度通常为 (O(log m))。若模数是合数，再加上 (O(sqrt m)) 的时间求欧拉函数。

求解多个数的乘法逆元

质数域下的连续递推法

若模数 (p) 为素数，而我们需要求出所有从 (1) 到 (p-1) 的逆元，那么有一个递推公式可以解决此问题，一次遍历搞定——时间复杂度仅为 (O(p))。这比 (O(plog p)) 一个一个求解的多次快速幂或扩展欧几里得快得多。

1. 初始化，用 (mathrm{inv}) 表示一个数的逆元，那么

   [ mathrm{inv}[1] = 1. ]

2. 对于每个 (2 le i le p-1)，因为

   [p = bigllfloortfrac p ibigrrfloorcdot i + (pbmod i) ;Longrightarrow; (pbmod i)equiv -bigllfloortfrac p ibigrrfloor,ipmod p. ]

   左右都乘以 (mathrm{inv}[p bmod i]timesmathrm{inv}[i])，得到

   [ mathrm{inv}[i] equiv - lfloortfrac p irfloor times mathrm{inv}!bigl[p bmod ibigr]pmod p. ]

   为了保证结果为正，改写为

   [ mathrm{inv}[i] = bigl(p - lfloortfrac p irfloor bigr)times mathrm{inv}!bigl[p bmod ibigr];bmod p. ]

这就意味着，可以总是用已推出的 (mathrm{inv}[p bmod i]) 来计算 (mathrm{inv}[i])。模数是素数保证了每个逆元的存在性（若模数为合数则此方法不可用）。

// 仅适用于素数模 p inv[1] = 1 for i = 2 to p-1:     inv[i] = (p - (p // i)) * inv[p mod i] mod p // 结束后 inv[i] 即为 i^{-1} mod p 

显然这样的时间是 (O(p))，空间也是 (O(p))。此法特别适合当你固定素数模 (p)，需要预处理所有小于 (p) 的逆元供后续 (O(1)) 查表时使用。

离线批量求逆元

如果要求多个较大且并不连续的逆元，上面的方法就不再可用，但是其实还有办法批量离线处理来加速计算。只需一次求逆和 (O(n)) 次乘法，就能在 (O(n + log m)) 时间内完成所有逆元计算。

• 令输入序列为 ({a_1,a_2,dots,a_n})，我们要求他们每个数的逆元。这个方法需要用到逆元的积性，所以首先构造前缀积数组

  [ P_0 = 1,quad P_i = a_1a_2cdots a_i bmod m,quad i=1ldots n. ]

• 仅对 (P_n = a_1a_2cdots a_n) 调用一次逆元算法，得到

  [ R_n = P_n^{-1} bmod m. ]

• 为了得到所有数的逆元，再倒过来枚举，逆序计算每个 (a_i^{-1})：

  [ a_i^{-1} ;=; R_i , P_{i-1} bmod m,quad i=n,n-1,dots,1. ]

  其中 (R_i) 表示从后缀开始累积的逆元乘积，初始 (R_{n}=P_{n}^{-1})，然后也由递推计算

  [ R_{i-1} = R_i times a_i bmod m,quad i=n,n-1,dots,1. ]

// 输入: a[1..n], 模数 m，且 ∀i: gcd(a[i], m)=1 P[0] = 1 for i = 1 to n:     P[i] = P[i-1] * a[i] mod m  // 一次求逆 R = inverse(P[n], m)  // 用扩展欧几里得或快速幂  // 逆序还原 for i = n down to 1:     inv[i] = R * P[i-1] mod m     R = R * a[i] mod m  return inv[1..n] 

时间复杂度：构造前缀积和逆序还原显然 (O(n))；一次求逆花费(O(log m))；总计 (O(n + log m))。空间复杂度 (O(n))。不要求质数模数，但要求逆元必须存在（所有 (a_i) 必须与 (m) 互质）。

本方案适合大批量逆元需求。将“逆元”操作的整体成本降至与单次求逆相近。

用逆元进行有理数取模

借助乘法逆元，我们现在不仅能对整数取模，还能给有理数取模。对于有理数 (dfrac{a}{b})（其中 (a,b) 可先取 $ bmod m$），若 (gcd(b,m)=1) 则有

[frac{a}{b} bmod m ;=; a times b^{-1} bmod m. ]

这里的 (b^{-1}) 就是前面各节讨论的“乘法逆元”。

• 分母须可逆：仅当 (gcd(b,m)=1) 时，才存在 (b^{-1}pmod m)。
• 分子可任意：对 (a) 先做 (a bmod m)，再与 (b^{-1}) 相乘。

如果 (gcd(b,m)>1)，则 (tfrac{a}{b}bmod m) 无意义——分母无论如何消不去。

例题：计算 (frac{3}{4}bmod7)

• 先求 (4^{-1}bmod7)。因 (4times2equiv1pmod7)，故 (4^{-1}=2)。

• 再计算：

  [ frac{3}{4}bmod7 = 3 times 2 bmod7 = 6. ]