查看“︁模反元素”︁的源代码

{{noteTA
|G1=Math
}}

'''模逆元'''（Modular multiplicative inverse）也称为'''模倒数'''、'''数论倒数'''。

一[[整数]]<math>a</math>對[[同餘]]<math>n</math>之模反元素是指滿足以下公式的整數<math>b</math>
:<math>a^{-1} \equiv b \pmod{n}.</math>

也可以寫成
:<math>ab \equiv 1 \pmod{n}.</math>
或者
:<math>ab \mod{n} = 1</math>

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

== 求模反元素 ==
=== 用[[扩展欧几里得算法]] ===

设<math>\mathrm{exgcd}(a,n)</math>為扩展欧几里得算法的函数，則可得到<math>ax+ny=g</math>，<math>g</math>是<math>a</math>, <math>n</math>的[[最大公因数]]。

==== 若g=1 ====
则该模反元素存在，根據結果<math>ax+ny=1</math>

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

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

==== 若 g≠1 ====
则该模反元素''不存在''。

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

=== 用[[歐拉定理 (數論)|歐拉定理]] ===

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

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

== 举例 ==
求整数3对同余11的模逆元素<math>x</math>,
:<math>x \equiv 3^{-1} \pmod{11}</math>
上述方程可变换为
:<math>3x \equiv 1 \pmod{11}</math>
在整数范围<math>\mathbb{Z}_{11}</math>内，可以找到满足该同余等式的''<math>x</math>''值为4，如下式所示
:<math>3 (4) = 12 \equiv 1 \pmod{11}</math>
并且，在整数范围<math>\mathbb{Z}_{11}</math>内不存在其他满足此同余等式的值。<br />

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

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

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

:<math>4 + (11 \cdot z ), z \in \mathbb{Z}</math>

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

{{algebra-stub}}
{{numtheory-stub}}

[[Category:同余]]