模逆

整數 (模 ) 的模逆是整數 ，使得

模逆可以使用 Wolfram 語言 計算，使用ModularInverse[b, m] 或PowerMod[b,-1, m]。

對於素數 和非 的倍數的 ，每個非零整數 都有一個逆元（模 ）。 例如，1、2、3 和 4 (mod 5) 的模逆分別是 1、3、2 和 4。

如果 不是素數，則並非每個非零整數 都有模逆。 實際上，非零整數 模 有模逆 當且僅當 和 互質。 例如， (mod 4) 和 (mod 4)，但 2 沒有模逆。

上面的三角形（OEIS A102057）給出了 (mod ) 對於 , 2, ..., 和 , 3, ... 的模逆。 0 表示不存在模逆。

如果 和 互質，則存在整數 和 使得 ，並且可以使用 歐幾里得演算法 找到這些整數。 考慮模 的這個方程，得出 ； 即 。

如果 和 互質，則 尤拉定理 指出 ，其中 是 尤拉函式。 因此，。