乘法反元素計算機

乘法反元素計算機

成長中 AI Skill PRO

輸入計算

保持 0 或留空即可求一般的倒數 1/a。

數學公式

數值 (a)·a−1≡1(mod模數 (m))\text{數值 (a)} \cdot a^{-1} \equiv 1 \pmod{\text{模數 (m)}}
使用統計

廣告

結果

的模反元素 7 mod 26
15
a · x ≡ 1 (mod m)
輸入數值 (a) 7
模數 (m) 26
倒數 (1/a) 0.142857

回報本頁錯誤

什麼是乘法反元素?

一個數的乘法反元素,就是與它相乘後結果為 1 的那個值。對一般的實數 \(a\) 來說,反元素就是它的倒數 \(1/a\)——舉例來說,4 的反元素是 0.25,因為 \(4 \times 0.25 = 1\)。而 0 沒有反元素,因為任何數乘以 0 都不可能等於 1。

數線展示一個數與其倒數相乘得到一
倒數 \(1/a\) 是與 \(a\) 相乘等於 1 的數。

模反元素

在模算術(同餘運算)中,\(a\) 對模 \(m\) 的乘法反元素,是介於 0 到 \(m-1\) 之間、且滿足 \(a \cdot x \equiv 1 \pmod{m}\) 的整數 \(x\)。這個概念在數論與密碼學中隨處可見(例如 RSA、雜湊運算、錯誤更正碼)。模反元素只有在 \(a\) 與 \(m\) 互質時才存在,也就是 \(\gcd(a, m) = 1\)。本計算機使用擴展歐幾里得演算法來求得它。

廣告
模運算時鐘錶盤,展示一個數乘以其反元素繞回到一
模反元素 \(x\) 滿足 \(a \cdot x \equiv 1 \pmod{m}\),以繞一圈 \(m\) 個位置的時鐘來表示。

如何使用本計算機

輸入你的數值 \(a\)。若把模數保持為 0(或留空),即可得到單純的倒數 \(1/a\)。若要計算模反元素,請輸入大於 1 的模數 \(m\);計算機會先將 \(a\) 對 \(m\) 取模,再回傳反元素,若 \(a\) 與 \(m\) 有公因數則會告訴你反元素不存在。

範例演算

求 3 對模 11 的反元素。我們要找出滿足 \(3x \equiv 1 \pmod{11}\) 的 \(x\)。試代入 \(x = 4\),得到 $$3 \times 4 = 12 = 11 + 1 \equiv 1 \pmod{11}.$$ 因此模反元素為 4。若看作倒數,3 的反元素則是 \(1/3 \approx 0.333333\)。

用擴展歐幾里得演算法手算模反元素

模 \(m\) 下 \(a\) 的模反元素,是滿足 \(a \cdot x \equiv 1 \pmod{m}\) 的數 \(x\)。它只在 \(\gcd(a, m) = 1\) 時存在。擴展歐幾里得演算法可以求出它。

  1. 執行歐幾里得演算法,對 \((m, a)\) 反覆做除法,每次把數對 \((m, a)\) 換成 \((a, r)\),其中 \(r\) 是餘數,直到餘數為 0。
  2. 檢查最大公因數。最後一個非零餘數就是 \(\gcd(a, m)\)。如果它不是 1,則不存在反元素,直接停止。
  3. 回代各除法列,寫出 \(1 = a \cdot x + m \cdot y\)。
  4. 將 \(x\) 對 \(m\) 取餘,化到 0 到 \(m-1\) 的範圍。若 \(x\) 為負數,加上 \(m\)。
  5. 驗證 \(a \cdot x \bmod m = 1\)。

範例:求 7 模 26 的反元素。

列 除法 商 餘數
1 26 = 3·7 + 5 3 5
2 7 = 1·5 + 2 1 2
3 5 = 2·2 + 1 2 1
4 2 = 2·1 + 0 2 0

最後一個非零餘數是 1,所以 \(\gcd(7, 26) = 1\),反元素存在。

從第 3 列開始回代:

$$1 = 5 - 2\cdot 2$$

由第 2 列代入 \(2 = 7 - 1\cdot 5\):

$$1 = 5 - 2(7 - 5) = 3\cdot 5 - 2\cdot 7$$

由第 1 列代入 \(5 = 26 - 3\cdot 7\):

$$1 = 3(26 - 3\cdot 7) - 2\cdot 7 = 3\cdot 26 - 11\cdot 7$$

所以 \(x = -11\)。取餘後得 \(-11 + 26 = \)15。

驗證:\(7 \cdot 15 = 105 = 4\cdot 26 + 1\),所以 \(105 \bmod 26 = 1\)。✓

廣告

倒數與模反元素:範例輸入比較

倒數 \(1/a\) 對每個非零實數都存在。模反元素只在 \(a\) 與 \(m\) 互質時存在。兩者是不同的量。

a 模數 m 倒數 1/a 模反元素 備註
3 11 0.3333 4 3·4 = 12 ≡ 1 (模 11)
4 8 0.25 無 最大公因數 gcd(4, 8) = 4,不是 1
7 26 0.142857 15 7·15 = 105 ≡ 1 (模 26)
−3 11 −0.3333 7 −3 在模 11 下化為 8,且 8·7 = 56 ≡ 1 (模 11)
0 任意 m > 1 未定義 無 0·x 永遠是 0,不會是 1

倒數不考慮模數。模反元素是介於 0 到 \(m-1\) 之間的整數,且只在 \(\gcd(a, m) = 1\) 時存在。

常見問題

為什麼 0 沒有反元素?因為任何數乘以 0 都會是 0,永遠不會等於 1。

模反元素在什麼情況下不存在?當 \(\gcd(a, m) \neq 1\) 時——例如 4 在模 8 之下沒有反元素,因為兩者共有因數 4。

模反元素可以使用負數嗎?可以;計算前會先把它化簡到 0 到 \(m-1\) 的範圍內,再進行求反元素。

最後更新:

數學和統計熱門計算器

查看全部數學和統計計算器