模逆元(Modular multiplicative inverse)也稱為模倒數、數論倒數。
一整數對同餘之模反元素是指滿足以下公式的整數
也可以寫成
或者
整數對模數之模反元素存在的充分必要條件是和互質,若此模反元素存在,在模數下的除法可以用和對應模反元素的乘法來達成,此概念和實數除法的概念相同。
求模反元素
設為擴展歐幾里得算法的函數,則可得到,是, 的最大公因數。
若g=1
則該模反元素存在,根據結果
在之下,,根據模反元素的定義,此時即為關於模的其中一個模反元素。
事實上, 都是關於模的模反元素,這裡我們取最小的正整數解()。
若 g≠1
則該模反元素不存在。
因為根據結果,在 之下,不會同餘於,因此滿足的不存在。
歐拉定理證明當為兩個互質的正整數時,則有,其中為歐拉函數(小於且與互質的正整數個數)。
上述結果可分解為,其中即為關於模之模反元素。
舉例
求整數3對同餘11的模逆元素,
上述方程可變換為
在整數範圍內,可以找到滿足該同餘等式的值為4,如下式所示
並且,在整數範圍內不存在其他滿足此同餘等式的值。
故,整數3對同餘11的模逆元素為4。
一旦在整數範圍內找到3的模逆元素,其他在整數範圍 內滿足此同餘等式的模逆元素值便可很容易地寫出——只需加上 的倍數便可。
綜上,所有整數3對同餘11的模逆元素x可表示為
即 {..., −18, −7, 4, 15, 26, ...}.