模逆元

模逆元也称为模倒数、数论倒数。

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

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

也可以写成

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

或者

$ab\mod {n}=1$

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

求模逆元

用扩展欧几里得算法

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

若g=1

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

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

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

若 g≠1

则该模逆元不存在。

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

用欧拉定理

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

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

举例

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

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

上述方程可变换为

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

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

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

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

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

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

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

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

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