如何計算模逆元？

最有效的方法是擴展歐幾里得演算法，該演算法可以找到整數 x 和 y，使得 ax + my = gcd(a, m)。當 gcd(a, m) = 1 時，x 即為模逆元。另外，如果 m 是質數，費馬小定理給出 a⁻¹ ≡ a^(m-2) (mod m)。

模逆元什麼時候不存在？

當 gcd(a, m) > 1 時，a (mod m) 的模逆元不存在。例如，6 (mod 9) 的逆元不存在，因為 gcd(6, 9) = 3 ≠ 1。

模逆元的實際用途有哪些？

模逆元是 RSA 加密、Diffie-Hellman 金鑰交換、橢圓曲線密碼學、求解線性同餘方程、中國剩餘定理計算以及計算模分數的基礎。

模乘逆元計算機

Q: 什麼是模乘逆元？

整數 a 模 m 的模乘逆元是一個整數 x，使得 a·x ≡ 1 (mod m)。它被表示為 a⁻¹ (mod m)，且當且僅當 gcd(a, m) = 1（即 a 和 m 互質）時存在。

使用擴展歐幾里得演算法計算整數 a 在模 m 下的模乘逆元，提供逐步計算表、驗證過程與時鐘視覺化。

模乘逆元計算機

Embed 模乘逆元計算機 Widget

模乘逆元計算機

什麼是模乘逆元？

整數 a 對於模數 m 的模乘逆元是指在 [0, m-1] 範圍內的一個整數 x，使得：

\( a \cdot x \equiv 1 \pmod{m} \)

它被寫作 a⁻¹ (mod m)，類似於普通算術中的乘法逆元（即 1/a），但應用於模運算領域。

關鍵條件： 逆元存在的當且僅當 gcd(a, m) = 1 — 也就是說，a 和 m 必須互質。

如何計算：擴展歐幾里得演算法

最有效的方法是使用擴展歐幾里得演算法。它能找到滿足貝祖等式的整數 x 和 y：

\( a \cdot x + m \cdot y = \gcd(a, m) = 1 \)

當 gcd(a, m) = 1 時，對等式兩邊取模 m 得到 a·x ≡ 1 (mod m)，因此 x 即為模逆元。

範例： 求 3⁻¹ (mod 7)：

擴展 GCD 給出：3·(5) + 7·(-2) = 15 − 14 = 1，因此 3⁻¹ ≡ 5 (mod 7)。驗證：3 × 5 = 15 = 2×7 + 1 ≡ 1 (mod 7) ✓

在密碼學與數學中的應用

🔐

RSA 加密

根據公鑰指數 e 尋找私鑰 d = e⁻¹ (mod φ(n))

📈

Diffie-Hellman

基於模運算中離散對數的金鑰交換協議

🇮

仿射密碼

解密時使用 a⁻¹ (mod 26) 來反轉加密金鑰

🔢

CRT 與數論

中國剩餘定理及求解線性同餘方程 ax ≡ b (mod m)

👑

橢圓曲線

ECC 中的點加法公式需要模逆元來計算斜率

📋

模分數

當 gcd(b, m) = 1 時，將 a/b (mod m) 計算為 a · b⁻¹ (mod m)

常見問題解答

問：為什麼逆元不總是存在？

因為模運算是「循環」的，a 的某些倍數可能永遠無法達到模 m 餘 1 的狀態。這種情況恰好發生在 a 和 m 有公因數時，即 gcd(a, m) > 1。

問：質數模數有公式嗎？

有的！如果 m 是質數且 a 不是 m 的倍數，費馬小定理給出： a⁻¹ ≡ a^m-2 (mod m)。這在競技程式設計中經常被使用。

問：結果是唯一的嗎？

是的，結果在模 m 下是唯一的。我們通常回報 [0, m-1] 範圍內的標準結果。其他有效的逆元為 x + km（k 為任何整數），但它們在模 m 下都是等價的。

問：如果 a 是負數怎麼辦？

該演算法可以處理負整數。在內部，我們會先計算 a (mod m) 以獲得一個非負的代表數，然後尋找其逆元。結果始終在 [0, m-1] 範圍內。

引用此內容、頁面或工具為：

"模乘逆元計算機" 於 https://MiniWebtool.com/zh-tw/模乘逆元計算機/，來自 MiniWebtool，https://MiniWebtool.com/

由 miniwebtool 團隊製作。更新日期：2026年2月18日

您還可以嘗試我們的 AI數學解題器 GPT，通過自然語言問答解決您的數學問題。

其他相關工具:

模乘逆元計算機

模乘逆元計算機

什麼是模乘逆元？

如何計算：擴展歐幾里得演算法

在密碼學與數學中的應用

常見問題解答

其他相關工具:

進階數學計算:

常用工具: