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

模反元素

维基百科,自由的百科全书
跳转至: 导航搜索

整数a對同餘n之模反元素是指滿足以下公式的整數 b

a^{-1} \equiv b \pmod{n}.

也可以寫成以下的式子

ab \equiv 1 \pmod{n}.

整数 a 對模数 n 之模反元素存在的充分必要條件是 a 和 n 互質,若此模反元素存在,在模数 n 下的除法可以用和對應模反元素的乘法來達成,此概念和實數除法的概念相同。

求法[编辑]

可以用扩展欧几里得算法求模反元素。

设exgcd(a,b)為扩展欧几里得算法的函数,exgcd接受两个整数a,b,输出結果ax+by=g,g是a,b的最大公约数

现在,利用扩展欧几里得算法計算exgcd(a,n),得到ax+ny=g

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 1a^{-1}不存在。


也可以用歐拉定理求模反元素

若a,b的最大公因數為1,則a^φ(b) ≡ 1 mod b,φ(N)為歐拉函數

顯然,a餘b的模反元素M為 a^(φ(b)-1)除以b的餘數

举例[编辑]

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

x \equiv 3^{-1} \pmod{11}

上述方程可变换为

3x \equiv 1 \pmod{11}

在整数范围\mathbb{Z}_{11}内,可以找到满足该同余等式的x值为4,如下式所示

3 (4) = 12 \equiv 1 \pmod{11}

并且,在整数范围\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, ...}.