模反元素

模反元素(Modular multiplicative inverse)也稱為模倒數數論倒數

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

也可以寫成

或者

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

求模反元素

 為擴展歐幾里得算法的函數,則可得到   ,  最大公因數

若g=1

則該模反元素存在,根據結果 

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

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

若 g≠1

則該模反元素不存在

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

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

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

舉例

求整數3對同餘11的模反元素 ,

 

上述方程式可轉換為

 

在整數範圍 內,可以找到滿足該同餘等式的 值為4,如下式所示

 

並且,在整數範圍 內不存在其他滿足此同餘等式的值。

故,整數3對同餘11的模反元素為4。

一旦在整數範圍 內找到3的模反元素,其他在整數範圍  內滿足此同餘等式的模反元素值便可很容易地寫出——只需加上  的倍數便可。

綜上,所有整數3對同餘11的模反元素x可表示為

 

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