求模逆元
设 为扩展欧几里得算法的函数,则可得到 , 是 , 的最大公因数。
若
则该模逆元存在,根据结果
在 之下, ,根据模逆元的定义 ,此时 即为 关于模 的其中一个模逆元。
事实上, 都是 关于模 的模逆元,这里我们取最小的正整数解 ( )。
若
则该模逆元不存在。
因为根据结果 ,在 之下, 不会同余于 ,因此满足 的 不存在。
用欧拉定理
欧拉定理证明当 为两个互素的正整数时,则有 ,其中 为欧拉函数(小于 且与 互素的正整数个数)。
上述结果可分解为 ,其中 即为 关于模 之模逆元。
举例
求整数3对同余11的模逆元素 ,
-
上述方程可变换为
-
在整数范围 内,可以找到满足该同余等式的 值为4,如下式所示
-
并且,在整数范围 内不存在其他满足此同余等式的值。
故,整数3对同余11的模逆元素为4。
一旦在整数范围 内找到3的模逆元素,其他在整数范围 内满足此同余等式的模逆元素值便可很容易地写出——只需加上 的倍数便可。
综上,所有整数3对同余11的模逆元素x可表示为
-
即 {..., −18, −7, 4, 15, 26, ...}.