模逆

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

模逆可以使用 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 表示不存在模逆。

如果 和 互质，则存在整数 和 使得 ，并且可以使用 欧几里得算法 找到这些整数。 考虑模 的这个方程，得出 ； 即 。

如果 和 互质，则 欧拉定理 指出 ，其中 是 欧拉函数。 因此，。