模逆元(Modular multiplicative inverse)也称为模倒数、数论倒数。
一整数
对同余
之模逆元是指满足以下公式的整数
![{\displaystyle a^{-1}\equiv b{\pmod {n}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/be54db4848231e9f72f61b746a27d6a0aeace369)
也可以写成
![{\displaystyle ab\equiv 1{\pmod {n}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/297023f006cd9486fa4192b391dbc819dd8f89e1)
或者
![{\displaystyle ab\mod {n}=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/79b108f18270119dd7336f3720dca1ef2c400b70)
整数
对模数
之模逆元存在的充分必要条件是
和
互素,若此模逆元存在,在模数
下的除法可以用和对应模逆元的乘法来达成,此概念和实数除法的概念相同。
求模逆元[编辑]
设
为扩展欧几里得算法的函数,则可得到
,
是
,
的最大公因数。
若g=1[编辑]
则该模逆元存在,根据结果
在
之下,
,根据模逆元的定义
,此时
即为
关于模
的其中一个模逆元。
事实上,
都是
关于模
的模逆元,这里我们取最小的正整数解
(
)。
若 g≠1[编辑]
则该模逆元不存在。
因为根据结果
,在
之下,
不会同余于
,因此满足
的
不存在。
欧拉定理证明当
为两个互素的正整数时,则有
,其中
为欧拉函数(小于
且与
互素的正整数个数)。
上述结果可分解为
,其中
即为
关于模
之模逆元。
求整数3对同余11的模逆元素
,
![{\displaystyle x\equiv 3^{-1}{\pmod {11}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0ac29204e8f6bf815124a12f607f63615b2b518f)
上述方程可变换为
![{\displaystyle 3x\equiv 1{\pmod {11}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7636a98a052c59e333721d7c5d572ba2257a66e4)
在整数范围
内,可以找到满足该同余等式的
值为4,如下式所示
![{\displaystyle 3(4)=12\equiv 1{\pmod {11}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/575ec18e419198b4efc4fe6a3832c2753ca50b2b)
并且,在整数范围
内不存在其他满足此同余等式的值。
故,整数3对同余11的模逆元素为4。
一旦在整数范围
内找到3的模逆元素,其他在整数范围
内满足此同余等式的模逆元素值便可很容易地写出——只需加上
的倍数便可。
综上,所有整数3对同余11的模逆元素x可表示为
![{\displaystyle 4+(11\cdot z),z\in \mathbb {Z} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/8dfa749fcc3e488282aadad6b744a8d2f59666fe)
即 {..., −18, −7, 4, 15, 26, ...}.