模反元素

模逆元（Modular multiplicative inverse）也称为模倒数、数论倒数。

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

也可以寫成

或者

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

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

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

 若g=1 
则该模反元素存在，根據結果

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

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

 若 g≠1 
则该模反元素不存在。

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

 用歐拉定理 

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

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

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

上述方程可变换为

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

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

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

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

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

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

Category:同余