模反元素

模逆元也称为模倒数数论倒数

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

也可以寫成

或者

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

求模反元素

扩展欧几里得算法

為扩展欧几里得算法的函数,則可得到, 最大公因数

若g=1

则该模反元素存在,根據結果

之下,,根據模反元素的定義,此時即為关于模的其中一個模反元素。

事實上, 都是关于模的模反元素,這裡我們取最小的正整數解)。

若 g≠1

则该模反元素不存在

因為根據結果,在 之下,不會同餘於,因此滿足不存在。

歐拉定理

歐拉定理證明當為兩個互質正整數時,則有,其中歐拉函數(小於且與互質的正整數個數)。

上述結果可分解為,其中即為關於模之模反元素。

举例

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

上述方程可变换为

在整数范围内,可以找到满足该同余等式的值为4,如下式所示

并且,在整数范围内不存在其他满足此同余等式的值。

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

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

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

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.