乘法逆元

若整数b，m互质，并且,则存在一个整数x，使得。称x为b的模m乘法逆元，记为。
因为,所以。
计算乘法逆元有两个方法费马小定理求解同余方程
如果m是质数，用p表示m并且b<p。根据费马小定理,即,就是b的模m乘法逆元。快速幂的时间求出乘法逆元，
如果b与m互质。那么乘法逆元通过求解同余方程,从另一个角度说，我们希望求解里的x，而这个方程有解的条件是。使用扩展欧几里得算法的时间计算出b的摸m乘法逆元。
乘法逆元可以用来计算除法，乘法和加法本身就可以取余运算，减法需要特判负数。乘方使用欧拉定理和欧拉降幂公式计算。