輸入一個數字和模，快速計算該數位在模下的逆元。
模逆元指的是在給定模 \( m \) 下，一個數字 \( a \) 的乘法逆元，即找到一個數 \( b \)，使得滿足 \( a \cdot b \equiv 1 \pmod{m} \)，模逆元在數論和密碼學中有廣泛應用。使用模逆元計算器，您可以輕鬆找到該數。
假設給定數位 \( a \) 和模 \( m \)，我們需要找到一個數字 \( b \)，使得： \( a \cdot b \equiv 1 \pmod{m} \)
計算步驟：
解答：
1. 確認互質性：
gcd(7, 26) = 1，說明 7 和 26 是互質的，因此模逆元存在。
2. 歐幾裡得算法求 gcd：
用歐幾裡得算法計算 gcd(7, 26) 並記錄每一步的係數：
最後一行得到的餘數是 1，因此 gcd(7, 26) = 1。
3. 反向替換求係數：
從倒數第二行開始回代，逐步用前一步的結果替代，直到得到表示 gcd 的公式：
\( 1 = 5 - 2 \times 2 \)
將 \( 2 \) 替換為 \( 7 - 1 \times 5 \)：
\( 1 = 5 - 2 \times (7 - 1 \times 5) = 3 \times 5 - 2 \times 7 \)
將 \( 5 \) 替換為 \( 26 - 3 \times 7 \)：
\( 1 = 3 \times (26 - 3 \times 7) - 2 \times 7 = 3 \times 26 - 11 \times 7 \)
因此，得到 \( 1 = 3 \times 26 - 11 \times 7 \)，即 \( -11 \) 是 7 的模 26 的逆元。
4. 結果歸一化：
為了得到正整數，調整 \( -11 \) 在模 26 的等價類，得到 \( -11 \equiv 15 \pmod{26} \)。
最終結果：7 在模 26 下的逆元是 15。
解答：
1. 確認互質性：
gcd(3, 11) = 1，說明 3 和 11 是互質的，因此模逆元存在。
2. 歐幾裡得算法求 gcd：
使用歐幾裡得算法計算 gcd(3, 11)：
最後一行得到的餘數是 1，因此 gcd(3, 11) = 1。
3. 反向替換求係數：
從倒數第二行開始回代：
\( 1 = 3 - 1 \times 2 \)
將 \( 2 \) 替換為 \( 11 - 3 \times 3 \)：
\( 1 = 3 - 1 \times (11 - 3 \times 3) = 4 \times 3 - 1 \times 11 \)
得到 \( 1 = 4 \times 3 - 1 \times 11 \)，即 \( 4 \) 是 3 的模 11 下的逆元。
最終結果：3 在模 11 下的逆元是 4。