2018-08-21

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

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

也可以写成以下的式子

如果不看mod运算,这类似于ab=1,那么a和b互为倒数。a、b为整数。 例如,对于模12来说,5和5互为模12的逆元。这是因为5*5=25 mod 12 = 1

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

求模反元素 `

用扩展欧几里得算法(Extended Euclidean algorithm)

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

若 $ g=1$

则该模反元素存在,根据结果$ ax+ny=1$

在 mod n 之下,$ ax+ny \equiv ax \equiv 1$,根据模反元素的定义$ a \cdot a^{-1} \equiv 1$,此时x即为a关于模n的其中一个模反元素。

事实上,$ x+kn(k \in \mathbb{Z})$ 都是a关于模n的模反元素,这里我们取最小的正整数解x mod n(x<n)。

若 $ g\ne 1$

则该模反元素’‘不存在’‘。

因为根据结果$ ax+ny\ne 1$,在 mod n 之下,$ ax \equiv g(g<n)$不会同余于$ 1$,因此满足$ a \cdot a^{-1} \equiv 1$的$ a^{-1}$不存在。

示例

已知整数a、b,扩展欧几里得算法可以在求得a、b的最大公约数的同时,能找到整数x、y(其中一个很可能是负数),使它们满足贝祖等式

$ ax + by = \gcd(a, b)$ 通常谈到最大公约数时,我们都会提到一个非常基本的事实:给予二个整数a、b,必存在整数x、y使得ax + by = gcd(a,b)

用类似辗转相除法,求二元一次不定方程 $ \textstyle 47x+30y=1$ 的整数解。

$\displaystyle 47=30\times 1+17$

$\displaystyle 30=17\times 1+13$

$\displaystyle 17=13\times 1+4$

$\displaystyle 13=4\times 3+1$$

然后把它们改写成“余数等于”的形式

$\displaystyle 17=47\times 1+30\times (-1)$ //式1

$\displaystyle 13=30\times 1+17\times (-1)$ //式2

$\displaystyle 4=17\times 1+13\times (-1)$ //式3

$\displaystyle 1=13\times 1+4\times (-3)$

然后把它们“倒回去”

$\displaystyle 1=13\times 1+4\times (-3)$

$\displaystyle 1=13\times 1+[17\times 1+13\times (-1)]*(-3)$ //应用式3

$\displaystyle 1=17\times (-3)+13\times 4$

$\displaystyle 1=17\times (-3)+[30\times 1+17\times (-1)]\times 4$//应用式2

$\displaystyle 1=30\times 4+17\times (-7)$

$\displaystyle 1=30\times 4+[47\times 1+30\times (-1)]\times (-7)$ //应用式1

$\displaystyle 1=47\times (-7)+30\times 11$

得解 $\displaystyle x=-7,y=11$。

用欧拉定理 (数论)|欧拉定理

欧拉定理证明当$ a,n$为两个互质正整数时,则有$ a^{\varphi(n)} \equiv 1 \pmod n$,其中$ \varphi(n)$为欧拉函数(小于等于$ n$且与$ n$互质的正整数个数)。

上述结果可分解为$ a^{\varphi(n)} = a \cdot a^{\varphi(n) - 1} \equiv 1 \pmod n$,其中$ a^{\varphi(n) - 1}$即为$ a$关于模$ n$之模反元素。

举例

求整数3对同余11的模逆元素’‘x’’, $ x \equiv 3^{-1} \pmod{11}$ 上述方程可变换为 $ 3x \equiv 1 \pmod{11}$ 在整数范围 $ \mathbb{Z}{11} $ 内,可以找到满足该同余等式的x值为4,如下式所示 并且,在整数范围 $ \mathbb{Z}{11} $ 内不存在其他满足此同余等式的值。

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

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

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

$ 4 + (11 \cdot z ), z \in \mathbb{Z}$

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

参考


如非注明转载, 均为原创. 本站遵循知识共享CC协议,转载请注明来源