模逆元

模逆元也称为模倒数

整数同余之模逆元是指满足以下公式的整数

也可以写成

或者

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

求模逆元

扩展欧几里得算法

 为扩展欧几里得算法的函数,则可得到   ,  最大公因数

 

则该模逆元存在,根据结果 

 之下, ,根据模逆元的定义 ,此时 即为 关于模 的其中一个模逆元。

事实上,  都是 关于模 的模逆元,这里我们取最小的正整数解  )。

 

则该模逆元不存在

因为根据结果 ,在  之下, 不会同余于 ,因此满足  不存在。

欧拉定理

欧拉定理证明当 为两个互素正整数时,则有 ,其中 欧拉函数(小于 且与 互素的正整数个数)。

上述结果可分解为 ,其中 即为 关于模 之模逆元。

举例

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

 

上述方程可变换为

 

在整数范围 内,可以找到满足该同余等式的 值为4,如下式所示

 

并且,在整数范围 内不存在其他满足此同余等式的值。

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

一旦在整数范围 内找到3的模逆元素,其他在整数范围  内满足此同余等式的模逆元素值便可很容易地写出——只需加上  的倍数便可。

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

 

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