热门问题
时间线
聊天
视角
模逆元
来自维基百科,自由的百科全书
Remove ads
Remove ads
模逆元(Modular multiplicative inverse)也称为模倒数、数论倒数。
也可以写成
或者
整数对模数之模逆元存在的充分必要条件是和互素,若此模逆元存在,在模数下的除法可以用和对应模逆元的乘法来达成,此概念和实数除法的概念相同。
Remove ads
求模逆元
设为扩展欧几里得算法的函数,则可得到,是, 的最大公因数。
Remove ads
则该模逆元存在,根据结果
在之下,,根据模逆元的定义,此时即为关于模的其中一个模逆元。
事实上, 都是关于模的模逆元,这里我们取最小的正整数解()。
则该模逆元不存在。
因为根据结果,在 之下,不会同余于,因此满足的不存在。
Remove ads
用欧拉定理
欧拉定理证明当为两个互素的正整数时,则有,其中为欧拉函数(小于且与互素的正整数个数)。
上述结果可分解为,其中即为关于模之模逆元。
Remove ads
举例
求整数3对同余11的模逆元素,
上述方程可变换为
在整数范围内,可以找到满足该同余等式的值为4,如下式所示
并且,在整数范围内不存在其他满足此同余等式的值。
故,整数3对同余11的模逆元素为4。
一旦在整数范围内找到3的模逆元素,其他在整数范围 内满足此同余等式的模逆元素值便可很容易地写出——只需加上 的倍数便可。
综上,所有整数3对同余11的模逆元素x可表示为
即 {..., −18, −7, 4, 15, 26, ...}.
![]() | 这是一篇关于代数的小作品。您可以通过编辑或修订扩充其内容。 |
![]() | 这是一篇关于数论的小作品。您可以通过编辑或修订扩充其内容。 |
Remove ads
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads