乘法逆元

定义

乘法逆元通常用于在同余式中进行除法运算,其内容为:若\(ax\equiv 1\pmod p\), 则称\(a\)在模\(p\)意义下的乘法逆元为\(x\)

求解算法

乘法逆元比较简单的三种求法:

费马小定理

由费马小定理\(a^{p-1}\equiv 1\pmod p\),其中\(p\)为质数; 得\(a\cdot a^{p-2}\equiv 1\pmod p\),于是\(a^{p-2}\)\(a\)的逆元。

扩展欧几里得算法

由逆元的定义可得方程\(ax+py=1\),用扩展欧几里得求解,适用于\(p\)不为质数的情况。

线性筛

线性筛

作者

xqmmcqs

发布于

2018-01-20

更新于

2022-06-09

许可协议

评论

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×