模乘逆元计算器

倒数 vs. 模乘逆元辨识

首先，对一个数 x,有一个 倒数 或者 乘逆元 , 记作 1/x 或者 x⁻¹, 它不同于 模 乘逆元。一个数x 的倒数是一个数，当乘以原 x 时，产生 1，称为乘法等式。你可以很容易地找到倒数。对于分数a/b，其乘法逆数是b/a。要找到一个实数的乘法倒数，只需用1除以该数。我认为在上述每种情况下都不需要任何特殊的计算器。但模乘逆元是另一回事，这就是为什么你可以看到我们下面的逆模计算器。理论可以在计算器之后找到。

逆模计算器

整数

模除

计算

模乘逆元

 

 链接  保存  小程序

模乘逆元

一个整数a模除m的模乘逆元是一个整数 b 因此
,
它可以表示为 , 在此不清楚是否倒数就是m模数。

当且仅当a和m是共质数（即如果gcd(a, m) = 1）时，a模除m的倒数存在。 如果a模除m的乘逆元存在，那么除以a模除m的运算就可以定义为乘以倒数。零没有模乘逆元。

a模除m的模乘逆元能在 扩展欧几里得算法中找到。

为了证明这一点，让我们看看这个等式::

这是有两个未知数的线性丢番图方程; 参见 线性丢番图方程求解器,为了求解，线性丢番图方程的右边应该是 的倍数。 由于1个只能被1整除而没有余数，所以上面的方程只有在时才有解。

可以用扩展欧几里得算法求解。一旦我们有了解，我们的x就是a模除m的模乘逆元，重写上面的方程如下

即

因此，x确实是a 模除 m的模乘逆元。