模反元素

模逆元也稱為模倒數、數論倒數。

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

$a^{-1}\equiv b{\pmod {n}}.$

也可以寫成

$ab\equiv 1{\pmod {n}}.$

或者

$ab\mod {n}=1$

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

求模反元素

用擴展歐幾里得算法

設$\mathrm {exgcd} (a,n)$為擴展歐幾里得算法的函數，則可得到$ax+ny=g$，$g$是$a$, $n$的最大公因數。

若g=1

則該模反元素存在，根據結果$ax+ny=1$

在${\bmod {n}}$之下，$ax+ny\equiv ax\equiv 1$，根據模反元素的定義$a\cdot a^{-1}\equiv 1$，此時$x$即為$a$關於模$n$的其中一個模反元素。

事實上，$x+kn(k\in \mathbb {Z} )$ 都是$a$關於模$n$的模反元素，這裡我們取最小的正整數解$x\mod n$（$x<n$）。

若 g≠1

則該模反元素不存在。

因為根據結果$ax+ny\neq 1$，在${\bmod {n}}$ 之下，$ax\equiv g(g<n)$不會同餘於$1$，因此滿足$a\cdot a^{-1}\equiv 1$的$a^{-1}$不存在。

用歐拉定理

歐拉定理證明當$a,n$為兩個互質的正整數時，則有$a^{\varphi (n)}\equiv 1{\pmod {n}}$，其中$\varphi (n)$為歐拉函數（小於$n$且與$n$互質的正整數個數）。

上述結果可分解為$a^{\varphi (n)}=a\cdot a^{\varphi (n)-1}\equiv 1{\pmod {n}}$，其中$a^{\varphi (n)-1}$即為$a$關於模$n$之模反元素。

舉例

求整數3對同餘11的模逆元素$x$,

$x\equiv 3^{-1}{\pmod {11}}$

上述方程可變換為

$3x\equiv 1{\pmod {11}}$

在整數範圍$\mathbb {Z} _{11}$內，可以找到滿足該同餘等式的$x$值為4，如下式所示

$3(4)=12\equiv 1{\pmod {11}}$

並且，在整數範圍$\mathbb {Z} _{11}$內不存在其他滿足此同餘等式的值。

故，整數3對同餘11的模逆元素為4。

一旦在整數範圍$\mathbb {Z} _{11}$內找到3的模逆元素，其他在整數範圍$\mathbb {Z}$ 內滿足此同餘等式的模逆元素值便可很容易地寫出——只需加上$m=11$ 的倍數便可。

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

$4+(11\cdot z),z\in \mathbb {Z}$

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