模反元素計算機（mod m）｜模逆運算工具

結果

Modular inverse a^-1 (mod m)

the integer x with a·x ≡ 1 (mod m)

gcd(a, m)	1
餘數範圍	0 ≤ x < m

什麼是模反元素計算機？

這個計算機能求出整數 a 對模數 m 的模反元素（modular multiplicative inverse），也就是位於 $0 \le x < m$ 範圍內、且滿足 $a \cdot x \equiv 1 \pmod{m}$ 的唯一整數 x。它採用擴展歐幾里得演算法（Extended Euclidean Algorithm），同時也會回傳 a 與 m 的最大公因數 $\gcd(a, m)$。這屬於純數論運算，在世界各地的計算結果都完全相同；它廣泛應用於密碼學（如 RSA 金鑰產生）、雜湊運算以及解線性同餘方程式。

使用方式

輸入整數 a 與一個正的模數 m（建議使用 $m \ge 2$，才會有有意義且唯一的反元素）。工具會先將 a 對 m 取模，再執行擴展歐幾里得演算法，最後一併顯示反元素與 $\gcd(a, m)$。若 a 與 m 並非互質（$\gcd \ne 1$），則反元素不存在，計算機會明確告知。

公式解析

反元素存在的充分必要條件是 $\gcd(a, m) = 1$。擴展歐幾里得演算法會找到整數 s 與 t，使得 $a \cdot s + m \cdot t = \gcd(a, m)$。當 gcd 為 1 時，$a \cdot s \equiv 1 \pmod{m}$，因此反元素為 $$x = ((s \bmod m) + m) \bmod m$$ 並化為最小的非負餘數。

圓形模環，展示 a 乘 x 繞回並落在 1 上 — 逆元 x 是使 a*x 繞模一圈後等於 1 的值。

範例演算

以 $a = 7$、$m = 4$ 為例：因為 $7 \equiv 3 \pmod{4}$，我們要解 $3x \equiv 1 \pmod{4}$。對 (7, 4) 執行擴展歐幾里得演算法，可得 $\gcd = 1$ 與貝祖係數（Bezout coefficient）$s = -1$，因此 $$x = ((-1 \bmod 4) + 4) \bmod 4 = 3$$ 驗證：$7 \cdot 3 = 21 = 5 \cdot 4 + 1 \equiv 1 \pmod{4}$。答案為 3。