模反元素
模反元素也称为模倒数,或者模逆元。
也可以寫成以下的式子
或者
- ab(mod n)=1
整数 a 對模数 n 之模反元素存在的充分必要條件是 a 和 n 互質,若此模反元素存在,在模数 n 下的除法可以用和對應模反元素的乘法來達成,此概念和實數除法的概念相同。
求模反元素编辑
用扩展欧几里得算法编辑
设exgcd(a,n)為扩展欧几里得算法的函数,則可得到ax+ny=g,g是a,n的最大公因数。
若 编辑
则该模反元素存在,根據結果
在 mod n 之下, ,根據模反元素的定義 ,此時x即為a关于模n的其中一個模反元素。
事實上, 都是a关于模n的模反元素,這裡我們取最小的正整數解x mod n(x<n)。
若 编辑
则该模反元素不存在。
因為根據結果 ,在 mod n 之下, 不會同餘於 ,因此滿足 的 不存在。
用歐拉定理编辑
歐拉定理證明當 為兩個互質的正整數時,則有 ,其中 為歐拉函數(小於等於 且與 互質的正整數個數)。
上述結果可分解為 ,其中 即為 關於模 之模反元素。
举例编辑
求整数3对同余11的模逆元素x,
上述方程可变换为
在整数范围 内,可以找到满足该同余等式的x值为4,如下式所示
并且,在整数范围 内不存在其他满足此同余等式的值。
故,整数3对同余11的模逆元素为4。
一旦在整数范围 内找到3的模逆元素,其他在整数范围 内满足此同余等式的模逆元素值便可很容易地写出——只需加上m = 11 的倍数便可。
综上,所有整数3对同余11的模逆元素x可表示为
即 {..., −18, −7, 4, 15, 26, ...}.
这是一篇關於代數的小作品。你可以通过编辑或修订扩充其内容。 |
这是一篇關於数论的小作品。你可以通过编辑或修订扩充其内容。 |