定义

对于正整数 ，满足 则是的乘法逆元，即 。

存在性

结论

存在 的乘法逆元，当且仅当 和 互质。

证明：

充分性（逆元->互质） 假设 和 存在公因数 ，即 。 设 。

由逆元的定义得到：

则

即

代入

由于 都是正整数，所以当且仅当 时，表达式成立，即 和 互质。

必要性（互质->逆元）

因为

以此递推，因为 和 互质，所以

换种写法:

从最后一条一条公式向上逆推，。依次将 代入式中，得到一个 的式子，通过变形（加、减 个 ）让 >0 。 则得到 是 关于 的乘法逆元。

求法

方法一、 拓展欧几里得法

其实上文必要性的证明，就是求解逆元的过程，下面举一个例子。 求7对于模19的乘法逆元

辗转相除:

逆推：

所以7对于模19的乘法逆元是11。

方法二、 费马小定理

费马小定理：如果是素数， 不能被 整除，则 。

化简后可以得到

即

其中

依然用求7对于模19的乘法逆元这个例子。

19是素数，则 。所以 7 关于模19的乘法逆元是 。