乘法逆元

何为乘法逆元？

对于两个数a,p" role="presentation" style="position: relative;">a,p$a,p$若gcd(a,p)=1" role="presentation" style="position: relative;">gcd(a,p)=1$gcd(a,p)=1$则一定存在另一个数b" role="presentation" style="position: relative;">b$b$，使得ab≡1(modp)" role="presentation" style="position: relative;">ab≡1(modp)$ab\equiv 1(\mathrm{mod}p)$，并称此时的b" role="presentation" style="position: relative;">b$b$为a" role="presentation" style="position: relative;">a$a$关于1" role="presentation" style="position: relative;">1$1$模p" role="presentation" style="position: relative;">p$p$的乘法逆元。我们记此时的b" role="presentation" style="position: relative;">b$b$为inv(a)" role="presentation" style="position: relative;">inv(a)$inv(a)$或a−1" role="presentation" style="position: relative;">a−1$a^{-1}$。 举个例子：5×3≡1(mod14)" role="presentation" style="position: relative;">5×3≡1(mod14)$5\times 3\equiv 1(\mathrm{mod}14)$，我们称此时的3" role="presentation" style="position: relative;">3$3$为5" role="presentation" style="position: relative;">5$5$关于1" role="presentation" style="position: relative;">1$1$模14" role="presentation" style="position: relative;">14$14$的乘法逆元。

如何求乘法逆元？

方法一：费马小定理

费马小定理：当有两数a,p" role="presentation" style="position: relative;">a,p$a,p$满足gcd(a,p)=1" role="presentation" style="position: relative;">gcd(a,p)=1$gcd(a,p)=1$时，则有ap≡a(modp)" role="presentation" style="position: relative;">ap≡a(modp)$a^p\equiv a(\mathrm{mod}p)$。 变一下形：a⋅ap−2≡1(modp)" role="presentation" style="position: relative;">a⋅ap−2≡1(modp)$a\cdot a^{p-2}\equiv 1(\mathrm{mod}p)$。是不是和上面的乘法逆元的定义是相似的？ 所以，我们可以使用快速幂求出ap−2" role="presentation" style="position: relative;">ap−2$a^{p-2}$，即求出a" role="presentation" style="position: relative;">a$a$的逆元。

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

由定义可知：ab≡1(modp)" role="presentation" style="position: relative;">ab≡1(modp)$ab\equiv 1(\mathrm{mod}p)$，这个式子等价于已知a,p" role="presentation" style="position: relative;">a,p$a,p$求一个二元一次不定方程ab=kp+1" role="presentation" style="position: relative;">ab=kp+1$ab=kp+1$，移一下项得：ab−kp=1" role="presentation" style="position: relative;">ab−kp=1$ab-kp=1$。这东西不是扩展欧几里得算法？

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

当我们要计算一大串连续的阶乘的逆元时，采用费马小定理或扩展欧几里得算法就有可能超时，所以我们必须采用一个更快的算法。 令fi=i!" role="presentation" style="position: relative;">fi=i!$f_i=i!$，则可得：inv(fi+1)≡inv(fi⋅(i+1))(modp)" role="presentation">inv(fi+1)≡inv(fi⋅(i+1))(modp)$$inv(f_{i+1})\equiv inv(f_i\cdot (i+1))(\mathrm{mod}p)$$
我们将(i+1)" role="presentation" style="position: relative;">(i+1)$(i+1)$乘过去，则有：inv(fi)≡inv(fi+1)⋅(i+1)(modp)" role="presentation">inv(fi)≡inv(fi+1)⋅(i+1)(modp)$$inv(f_i)\equiv inv(f_{i+1})\cdot (i+1)(\mathrm{mod}p)$$
自然我们就得出递推式。

乘法逆元的作用？

我们由费马