什麼是乘法反元素?
一個數的乘法反元素,就是與它相乘後結果為 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\)。
常見問題
為什麼 0 沒有反元素?因為任何數乘以 0 都會是 0,永遠不會等於 1。
模反元素在什麼情況下不存在?當 \(\gcd(a, m) \neq 1\) 時——例如 4 在模 8 之下沒有反元素,因為兩者共有因數 4。
模反元素可以使用負數嗎?可以;計算前會先把它化簡到 0 到 \(m-1\) 的範圍內,再進行求反元素。