模反元素

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

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

也可以寫成以下的式子

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

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

求模反元素

用扩展欧几里得算法

设exgcd(a,n)為扩展欧几里得算法的函数，則可得到ax+ny=g，g是a,n的最大公因数。

若$g=1$$g=1$

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

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

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

若$g\neq 1$$g\neq 1$

则该模反元素不存在。

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

用歐拉定理

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

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

举例

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

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

上述方程可变换为

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

在整数范围$\mathbb {Z} _{11}$${\mathbb {Z}}_{{11}}$内，可以找到满足该同余等式的x值为4，如下式所示

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

并且，在整数范围$\mathbb {Z} _{11}$${\mathbb {Z}}_{{11}}$内不存在其他满足此同余等式的值。

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

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

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

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

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