乘法逆元

· · 个人记录

p.s：转自：https://blog.csdn.net/qq_37656398/article/details/81434277

乘法逆元

何为乘法逆元？

对于两个数a,p，若gcd(a,p)=1

则一定存在另一个数b，使得ab≡1(modp)，

并称此时的b为a关于1模p的乘法逆元。我们记此时的b 为inv(a)或a−1（次方）

如何求乘法逆元？

方法一：费马小定理

方法二：扩展欧几里得算法

方法三：递推计算阶乘的逆元

方法四：递推计算连续的数的逆元