Modular Inverse

定义 Definition

模逆元 / 模反元素：在模运算中，若对给定整数 \(a\) 和模数 \(m\)，存在整数 \(x\) 使得
\[ a \cdot x \equiv 1 \pmod m \] 则称 \(x\) 是 \(a\) 在模 \(m\) 下的 modular inverse（模逆元）。一般只有当 \(\gcd(a,m)=1\)（互素）时，模逆元才存在。
（在某些语境里也会简称为 inverse mod \(m\) 或 multiplicative inverse modulo \(m\)。）

发音 Pronunciation (IPA)

/ˈmɑːdjələr ˈɪnvɜːrs/

例句 Examples

We need the modular inverse of 3 modulo 11.
我们需要求 3 在模 11 下的模逆元。

Using the extended Euclidean algorithm, you can compute a modular inverse efficiently even for large numbers in cryptography.
使用扩展欧几里得算法，即使在密码学中的大整数场景，也能高效计算模逆元。

词源 Etymology

modular 来自 modulus（“模、尺度”），与“取模运算/模系统”有关；inverse 源自拉丁语 inversus（“倒转的、相反的”）。合在一起表示“在模意义下的乘法逆（使结果回到 1 的那个数）”。

相关词 Related Words

• Modulus
• Modulo
• Congruence
• Residue
• Coprime
• Greatest Common Divisor
• Extended Euclidean Algorithm
• Euler Totient
• Modular Arithmetic
• Cryptography

文学与著作 Literary Works

• An Introduction to the Theory of Numbers（G. H. Hardy & E. M. Wright）——数论基础中讨论同余与逆元等概念。
• A Computational Introduction to Number Theory and Algebra（Victor Shoup）——以计算视角系统讲解模逆元及其算法。
• Applied Cryptography（Bruce Schneier）——在公钥密码与实现细节中频繁用到模逆元。
• *Introduction to Algorithms (CLRS)*（Cormen et al.）——算法章节涉及扩展欧几里得算法与相关模运算思想。