对于正整数 a, x, m，如果满足 ax=1(modm) ，那么我们就称 x 是同余方程中 a 模 m 的逆元。
求乘法逆元：
- 费马小定理求逆元
p为一个素数，且 (a, p) = 1，则有 ap−1=1(modp) 。
那么 a 的一个乘法逆元为 ap−2 . - 拓展GCD求乘法逆元
a * x + b * y = gcd(a, b)
取质数 m，使得 (a, m) = 1，令 b = m 带入
a * x + m * y = 1
x 就是 同余方程中 a 的乘法逆元。 - 欧拉定理求乘法逆元
在 费马小定理 和 拓展GCD 中都有局限性，必须要求 m 为质数。而我们知道欧拉定理中 (a, m) = 1，有 aϕ(m)=1(modm) 。
那么很容易就知道： aϕ(m)−1 就是 a 的一个乘法逆元。
一般应用：
ax=1(modm)
故 x=1a(modm)
因此要求 ba(modm) ，就可以求 b∗x(modm) ，所以求出 (b(modm)∗x(modm))(modm) 即可。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/199499.html原文链接：https://javaforall.net
