模反元素

模逆元（Modular multiplicative inverse）也稱為模倒數、數論倒數。

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

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

也可以寫成

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

或者

${\displaystyle ab\mod {n}=1}$

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

求模反元素

用擴展歐幾里得算法

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

若g=1

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

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

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

若 g≠1

則該模反元素不存在。

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

用歐拉定理

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

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

舉例

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

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

上述方程可變換為

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

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

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

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

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

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

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

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

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