本页使用了标题或全文手工转换

模逆元

维基百科,自由的百科全书
跳到导航 跳到搜索

模逆元也称为模倒数,或者模逆元

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

也可以写成以下的式子

或者

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

求模逆元[编辑]

扩展欧几里得算法[编辑]

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

[编辑]

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

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

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

[编辑]

则该模逆元不存在

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


欧拉定理[编辑]

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

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

举例[编辑]

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

上述方程可变换为

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

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

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

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

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

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