模反元素計算器（模逆元）

輸入計算

整數 a

模數 m

結果

模反元素

4

a^-1 mod m

gcd(a, m)	1
模反元素存在	是

什麼是模 m 的模反元素？

整數 a 對模數 m 的模反元素（又稱模逆元），是一個介於 1 到 m−1 之間的整數 x，使得 \((a \cdot x) \bmod m = 1\)。換句話說，把 a 乘以 x 之後再除以 m，餘數恰好等於 1。它相當於模算術中「除以 a」的運算，也是數論與密碼學的重要基石——RSA 金鑰產生、雜湊（Hashing）、中國剩餘定理等都會用到它。

Modular arithmetic wraps the number line into a circle of m positions.

如何使用這個計算器

輸入整數 a 與模數 m（m 必須大於或等於 2）。計算器會先將 a 對 m 取餘數，再執行擴展歐幾里得演算法，若模反元素存在便會回傳結果。當 a 為負數時，系統會自動將其化簡到 0 到 m−1 的範圍內，無需另行處理。

公式原理解析

模反元素存在的充分必要條件是 \(\gcd(a, m) = 1\)——也就是 a 與 m 除了 1 以外沒有其他公因數（兩者互質）。擴展歐幾里得演算法可以找出滿足 \(a \cdot s + m \cdot t = \gcd(a, m)\) 的整數 s 與 t。當最大公因數為 1 時，將係數 s 對 m 取餘數，得到的就是模反元素；若 \(\gcd(a, m) \neq 1\)，則模反元素不存在。

$$\text{a} \cdot x \equiv 1 \pmod{\text{m}}, \quad x \text{ exists } \iff \gcd\!\left(\text{a},\, \text{m}\right) = 1$$

The extended Euclidean algorithm yields x satisfying a·x + m·y = 1.

實際範例

求 3 對模數 11 的模反元素。我們要找到 x 使得 \((3 \cdot x) \bmod 11 = 1\)。試算可得 \(3 \cdot 4 = 12\)，而 \(12 \bmod 11 = 1\)，所以模反元素是 4。由於 \(\gcd(3, 11) = 1\)，擴展歐幾里得演算法能瞬間得到相同的結果。

Multiplying a by its inverse x lands exactly on 1 after wrapping mod m.

常見問題

什麼情況下沒有模反元素？當 a 與 m 不互質時。例如 4 在模 8 之下沒有模反元素，因為 \(\gcd(4, 8) = 4 \neq 1\)。

模數一定要是質數嗎？不必。只要 a 與模數互質，任何模數都可以。如果 m 是質數，那麼從 1 到 m−1 的每個非零整數 a 都會有模反元素。

為什麼結果一定介於 1 到 m−1 之間？因為我們會將模反元素對 m 取餘數，以呈現最小正餘數這個標準（規範）形式。