模逆元（Modular multiplicative inverse）也称为模倒数、数论倒数。
一整数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）。
若 g≠1
则该模反元素不存在。
因為根據結果ax+ny\ne 1，在\bmod n 之下，ax \equiv g(g不會同餘於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, ...}.
评论 (0)