模乘逆元计算器
逆元计算器计算一个给定整数a 模除 m 的模乘逆元。
本内容采用知识共享署名/相同方式共享许可协议3.0（未移植）进行许可。这意味着你可以在相同的许可条件下自由地重新发布或修改本内容，并且必须在你的网站上放置一个超链接到本作品https://zh.planetcalc.com/3311/，以注明原作者。此外，请不要修改本内容中对原作的任何引用（如果有的话）。
倒数 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的模乘逆元。
URL 复制到剪贴板
类似计算器
PLANETCALC, 模乘逆元计算器
评论