模反元素(Modular multiplicative inverse)也稱為模倒數、數論倒數。
一整數
對同餘
之模反元素是指滿足以下公式的整數
![{\displaystyle a^{-1}\equiv b{\pmod {n}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/be54db4848231e9f72f61b746a27d6a0aeace369)
也可以寫成
![{\displaystyle ab\equiv 1{\pmod {n}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/297023f006cd9486fa4192b391dbc819dd8f89e1)
或者
![{\displaystyle ab\mod {n}=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/79b108f18270119dd7336f3720dca1ef2c400b70)
整數
對模數
之模反元素存在的充分必要條件是
和
互質,若此模反元素存在,在模數
下的除法可以用和對應模反元素的乘法來達成,此概念和實數除法的概念相同。
求模反元素[編輯]
設
為擴展歐幾里得算法的函數,則可得到
,
是
,
的最大公因數。
若g=1[編輯]
則該模反元素存在,根據結果
在
之下,
,根據模反元素的定義
,此時
即為
關於模
的其中一個模反元素。
事實上,
都是
關於模
的模反元素,這裏我們取最小的正整數解
(
)。
若 g≠1[編輯]
則該模反元素不存在。
因為根據結果
,在
之下,
不會同餘於
,因此滿足
的
不存在。
歐拉定理證明當
為兩個互質的正整數時,則有
,其中
為歐拉函數(小於
且與
互質的正整數個數)。
上述結果可分解為
,其中
即為
關於模
之模反元素。
求整數3對同餘11的模反元素
,
![{\displaystyle x\equiv 3^{-1}{\pmod {11}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0ac29204e8f6bf815124a12f607f63615b2b518f)
上述方程可轉換為
![{\displaystyle 3x\equiv 1{\pmod {11}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7636a98a052c59e333721d7c5d572ba2257a66e4)
在整數範圍
內,可以找到滿足該同餘等式的
值為4,如下式所示
![{\displaystyle 3(4)=12\equiv 1{\pmod {11}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/575ec18e419198b4efc4fe6a3832c2753ca50b2b)
並且,在整數範圍
內不存在其他滿足此同餘等式的值。
故,整數3對同餘11的模反元素為4。
一旦在整數範圍
內找到3的模反元素,其他在整數範圍
內滿足此同餘等式的模反元素值便可很容易地寫出——只需加上
的倍數便可。
綜上,所有整數3對同餘11的模反元素x可表示為
![{\displaystyle 4+(11\cdot z),z\in \mathbb {Z} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/8dfa749fcc3e488282aadad6b744a8d2f59666fe)
即 {..., −18, −7, 4, 15, 26, ...}.