模反元素計算機

模反元素計算機

成長中 AI Skill PRO

輸入計算

結果

模反元素
2,753
滿足 (a·x) mod m = 1 的 x
反元素存在 是
gcd(a, m) 1

數學公式

a·x≡1(modm)⟹x=a−1modm\text{a} \cdot x \equiv 1 \pmod{\text{m}} \quad\Longrightarrow\quad x = \text{a}^{-1} \bmod \text{m}
使用統計

廣告

回報本頁錯誤

什麼是模反元素?

整數 a 對模數 m 的模乘法反元素,是指一個整數 x,使得 \((a \cdot x) \bmod m = 1\) 成立。它相當於模運算中的「除法」,在數論、RSA 加密系統以及許多編碼理論演算法中都扮演關鍵角色。本計算機透過擴展歐幾里得演算法(extended Euclidean algorithm)求出 x。

數線環繞著時鐘般的圓形模數環,顯示 a 乘 x 落在 1 上
模反元素 x 與 a 相乘後將 a 映回 1,在模 m 上循環繞回。

如何使用本計算機

輸入數字 a 與模數 m(m ≥ 2)。工具會回傳落在 0 ≤ x < m 範圍內、最小的非負反元素 x,並確認反元素是否存在,同時顯示 gcd(a, m)。若 gcd(a, m) ≠ 1,代表反元素不存在,結果會顯示為「無」。

公式說明

反元素只有在 \(\gcd(a, m) = 1\) 時才存在,也就是 a 與 m 互質。擴展歐幾里得演算法會找出滿足 \(a \cdot x + m \cdot y = \gcd(a, m)\) 的整數 x 與 y。當最大公因數為 1 時,把 x 對 m 取模即可得到反元素。若結果為負,再加上 m 即可正規化為正值。

$$\text{a} \cdot x \equiv 1 \pmod{\text{m}} \quad\Longrightarrow\quad x = \text{a}^{-1} \bmod \text{m}$$
廣告
擴展歐幾里得演算法步驟的扁平流程圖,產生最大公因數與係數
擴展歐幾里得演算法給出係數,當 gcd(a, m) = 1 時即得反元素。

實際範例

求 3 對模數 11 的反元素。我們要找出滿足 \(3x \equiv 1 \pmod{11}\) 的 x。試算一下,

$$3 \times 4 = 12 = 11 + 1 \quad\Longrightarrow\quad 12 \bmod 11 = 1$$

因此 x = 4。擴展歐幾里得演算法也會得到相同結果,而 \(\gcd(3, 11) = 1\),證明反元素確實存在。

逐步說明:手算擴展歐幾里得演算法

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

  1. 重複除法。 用 m 除以 a,再用前一個除數除以餘數,依此類推,直到餘數為 0。最後一個非零餘數就是最大公因數。若它不是 1,則不存在反元素。
  2. 將 1 表示為組合。 逆向代入(回代),或在計算過程中追蹤係數,寫出 \(1 = a \cdot x + m \cdot y\)。這就是貝祖等式(Bézout identity)。
  3. 化簡 x。 取 \(x \bmod m\)。若 x 為負數,則加上 m(必要時重複),使其落在 0 到 m − 1 的範圍內。

實例:a = 7,m = 40。

步驟 除法 商 q 餘數
1 40 = 5·7 + 5 5 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, 40) = 1\),反元素存在。

回代:

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

因此 \(7 \cdot (-17) + 40 \cdot 3 = 1\),得到 \(x = -17\)。

迭代檢驗(a 的係數 t): 從 \(t_0 = 0\)(m = 40)與 \(t_1 = 1\)(a = 7)開始,然後使用 \(t_{k+1} = t_{k-1} - q_k \, t_k\)。

餘數 使用的 q t
40 – 0
7 – 1
5 5 0 − 5·1 = −5
2 1 1 − 1·(−5) = 6
1 2 −5 − 2·6 = −17

餘數達到 1 的那一列給出 \(t = -17\)。化簡:\(-17 + 40 = \)23。

驗算: \(7 \cdot 23 = 161 = 4 \cdot 40 + 1\),所以 \(161 \bmod 40 = 1\)。✓

同樣的方法也適用於較大的數。對於 a = 17、m = 3120,它得到 x = 2753,因為 \(17 \cdot 2753 = 46801 = 15 \cdot 3120 + 1\)。這組數是經典的 RSA 教科書範例。

輸入範例及其反元素

下列每個反元素都滿足 \((a \cdot x) \bmod m = 1\)。當 \(\gcd(a, m) > 1\) 時,不存在反元素。

a m gcd(a, m) 反元素 x 驗算
3 11 1 4 3·4 = 12 = 1·11 + 1
7 26 1 15 7·15 = 105 = 4·26 + 1
5 12 1 5 5·5 = 25 = 2·12 + 1
10 17 1 12 10·12 = 120 = 7·17 + 1
17 3120 1 2753 17·2753 = 46801 = 15·3120 + 1
4 6 2 無 4x mod 6 永遠是偶數,永遠不會是 1
6 9 3 無 6x mod 9 永遠是 3 的倍數,永遠不會是 1

注意到 5 是它自己在模 12 下的反元素。一般而言,\(x^2 \equiv 1 \pmod{m}\) 除了 1 之外還有其他解,因此某些數是自反元素(即自身的反元素)。

廣告

關鍵術語:互質、GCD、同餘與剩餘

  • 模數 (m): 數值循環繞回的正整數,就像時鐘面上的數字。
  • 同餘 (≡): \(a \equiv b \pmod{m}\) 表示 m 整除 \(a - b\),因此 a 與 b 除以 m 的餘數相同。
  • GCD: 最大公因數,即能同時整除兩個數的最大整數。
  • 互質(relatively prime): gcd 為 1 的兩個整數。這正是模反元素存在的條件。
  • 貝祖等式(Bézout identity): 對整數 a 與 m,存在整數 x 與 y 使得 \(a \cdot x + m \cdot y = \gcd(a, m)\)。當 gcd 為 1 時,將此等式對 m 取模得到 \(a \cdot x \equiv 1\),因此 x 即為反元素。
  • 剩餘類: 所有與某數模 m 餘數相同的整數所組成的集合。反元素作為剩餘類是唯一的,計算器回報的是 0 到 m − 1 之間的代表元。
  • 模乘法反元素: 滿足 \(a \cdot x \equiv 1 \pmod{m}\) 的剩餘 \(x = a^{-1} \bmod m\)。

歐拉定理: 若 \(\gcd(a, m) = 1\),則 \(a^{\varphi(m)} \equiv 1 \pmod{m}\),其中 \(\varphi\) 是歐拉函數(Euler's totient function)。因此反元素也可以計算為 \(a^{\varphi(m)-1} \bmod m\)。

費馬小定理: 當 m = p 為質數時,\(\varphi(p) = p - 1\),因此對於任何不被 p 整除的 a,\(a^{-1} \equiv a^{p-2} \pmod{p}\)。例:\(3^{9} = 19683 = 1789 \cdot 11 + 4\),所以 \(3^{-1} \equiv 4 \pmod{11}\),與上表一致。冪次公式需要 m 的因數分解(以求出 \(\varphi\)),而擴展歐幾里得演算法不需要,因此對一般模數而言通常較快。

常見問題

什麼情況下反元素不存在?當 a 與 m 有大於 1 的公因數時——例如 4 對模數 6(gcd = 2)就沒有反元素。

m 一定要是質數嗎?不必。m 可以是任何 ≥ 2 的整數;重點只在於 a 與 m 是否互質。

答案會落在什麼範圍?反元素以最小的非負剩餘形式給出,介於 0 與 m − 1 之間。

最後更新:

數學和統計熱門計算器

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