模逆元

(重定向自模逆元

模逆元(Modular multiplicative inverse)也称为模倒数数论倒数

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

也可以写成

或者

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

求模逆元

编辑

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

若g=1

编辑

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

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

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

若 g≠1

编辑

则该模逆元不存在

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

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

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

举例

编辑

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

 

上述方程可变换为

 

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

 

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

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

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

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

 

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