模逆元

模逆元（Modular multiplicative inverse）也称为模倒数、数论倒数。

一整数${\displaystyle a}$对同余${\displaystyle n}$之模逆元是指满足以下公式的整数${\displaystyle b}$

${\displaystyle a^{-1}\equiv b{\pmod {n}}.}$

也可以写成

${\displaystyle ab\equiv 1{\pmod {n}}.}$

或者

${\displaystyle ab\mod {n}=1}$

整数${\displaystyle a}$对模数${\displaystyle n}$之模逆元存在的充分必要条件是${\displaystyle a}$和${\displaystyle n}$互素，若此模逆元存在，在模数${\displaystyle n}$下的除法可以用和对应模逆元的乘法来达成，此概念和实数除法的概念相同。

求模逆元

用扩展欧几里得算法

设${\displaystyle \mathrm {exgcd} (a,n)}$为扩展欧几里得算法的函数，则可得到${\displaystyle ax+ny=g}$，${\displaystyle g}$是${\displaystyle a}$, ${\displaystyle n}$的最大公因数。

若g=1

则该模逆元存在，根据结果${\displaystyle ax+ny=1}$

在${\displaystyle {\bmod {n}}}$之下，${\displaystyle ax+ny\equiv ax\equiv 1}$，根据模逆元的定义${\displaystyle a\cdot a^{-1}\equiv 1}$，此时${\displaystyle x}$即为${\displaystyle a}$关于模${\displaystyle n}$的其中一个模逆元。

事实上，${\displaystyle x+kn(k\in \mathbb {Z} )}$ 都是${\displaystyle a}$关于模${\displaystyle n}$的模逆元，这里我们取最小的正整数解${\displaystyle x\mod n}$（${\displaystyle x<n}$）。

若 g≠1

则该模逆元不存在。

因为根据结果${\displaystyle ax+ny\neq 1}$，在${\displaystyle {\bmod {n}}}$ 之下，${\displaystyle ax\equiv g(g<n)}$不会同余于${\displaystyle 1}$，因此满足${\displaystyle a\cdot a^{-1}\equiv 1}$的${\displaystyle a^{-1}}$不存在。

用欧拉定理

欧拉定理证明当${\displaystyle a,n}$为两个互素的正整数时，则有${\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}}}$，其中${\displaystyle \varphi (n)}$为欧拉函数（小于${\displaystyle n}$且与${\displaystyle n}$互素的正整数个数）。

上述结果可分解为${\displaystyle a^{\varphi (n)}=a\cdot a^{\varphi (n)-1}\equiv 1{\pmod {n}}}$，其中${\displaystyle a^{\varphi (n)-1}}$即为${\displaystyle a}$关于模${\displaystyle n}$之模逆元。

举例

求整数3对同余11的模逆元素${\displaystyle x}$,

${\displaystyle x\equiv 3^{-1}{\pmod {11}}}$

上述方程可变换为

${\displaystyle 3x\equiv 1{\pmod {11}}}$

在整数范围${\displaystyle \mathbb {Z} _{11}}$内，可以找到满足该同余等式的${\displaystyle x}$值为4，如下式所示

${\displaystyle 3(4)=12\equiv 1{\pmod {11}}}$

并且，在整数范围${\displaystyle \mathbb {Z} _{11}}$内不存在其他满足此同余等式的值。

故，整数3对同余11的模逆元素为4。

一旦在整数范围${\displaystyle \mathbb {Z} _{11}}$内找到3的模逆元素，其他在整数范围${\displaystyle \mathbb {Z} }$ 内满足此同余等式的模逆元素值便可很容易地写出——只需加上${\displaystyle m=11}$ 的倍数便可。

综上，所有整数3对同余11的模逆元素x可表示为

${\displaystyle 4+(11\cdot z),z\in \mathbb {Z} }$

即 {..., −18, −7, 4, 15, 26, ...}.