什麼是乘法反元素?
一個數的乘法反元素,就是與它相乘後結果為 1 的那個值。對一般的實數 \(a\) 來說,反元素就是它的倒數 \(1/a\)——舉例來說,4 的反元素是 0.25,因為 \(4 \times 0.25 = 1\)。而 0 沒有反元素,因為任何數乘以 0 都不可能等於 1。
模反元素
在模算術(同餘運算)中,\(a\) 對模 \(m\) 的乘法反元素,是介於 0 到 \(m-1\) 之間、且滿足 \(a \cdot x \equiv 1 \pmod{m}\) 的整數 \(x\)。這個概念在數論與密碼學中隨處可見(例如 RSA、雜湊運算、錯誤更正碼)。模反元素只有在 \(a\) 與 \(m\) 互質時才存在,也就是 \(\gcd(a, m) = 1\)。本計算機使用擴展歐幾里得演算法來求得它。
如何使用本計算機
輸入你的數值 \(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\) 時存在。擴展歐幾里得演算法可以求出它。
- 執行歐幾里得演算法,對 \((m, a)\) 反覆做除法,每次把數對 \((m, a)\) 換成 \((a, r)\),其中 \(r\) 是餘數,直到餘數為 0。
- 檢查最大公因數。最後一個非零餘數就是 \(\gcd(a, m)\)。如果它不是 1,則不存在反元素,直接停止。
- 回代各除法列,寫出 \(1 = a \cdot x + m \cdot y\)。
- 將 \(x\) 對 \(m\) 取餘,化到 0 到 \(m-1\) 的範圍。若 \(x\) 為負數,加上 \(m\)。
- 驗證 \(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\) 的範圍內,再進行求反元素。