乘法逆元
定义
乘法逆元通常用于在同余式中进行除法运算,其内容为:若\(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\)不为质数的情况。