乘法逆元素详解 [费马小定理 + 扩展欧几里得算法］

乘法逆元

何为乘法逆元？

对于两个数$a,p$若$\gcd (a,p)=1$则一定存在另一个数$b$，使得$ab\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}p)$，并称此时的$b$为$a$关于$1$模$p$的乘法逆元。我们记此时的$b$为$inv(a)$或$a^{-1}$。

举个例子：$5\times 3\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}14)$，我们称此时的$3$为$5$关于$1$模$14$的乘法逆元。

如何求乘法逆元？

方法一：费马小定理

费马小定理：当有两数$a,p$满足$\gcd (a,p)=1$，$p$是质数时，则有$a^p\equiv a(\mathrm{m}\mathrm{o}\mathrm{d}p)$。

变一下形：$a\cdot a^{p-2}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}p)$。是不是和上面的乘法逆元的定义是相似的？

所以，我们可以使用快速幂求出$a^{p-2}$，即求出$a$的逆元。

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

由定义可知：$ab\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}p)$，这个式子等价于已知$a,p$求一个二元一次不定方程$ab=kp+1$，移一下项得：$ab-kp=1$。这东西不是扩展欧几里得算法？

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

当我们要计算一大串连续的阶乘的逆元时，采用费马小定理或扩展欧几里得算法就有可能超时，所以我们必须采用一个更快的算法。

令$f_i=i!$，则可得：$$inv(f_{i+1})\equiv inv(f_i\cdot (i+1))(\mathrm{m}\mathrm{o}\mathrm{d}p)$$

我们将$(i+1)$乘过去，则有：$$inv(f_i)\equiv inv(f_{i+1})\cdot (i+1)(\mathrm{m}\mathrm{o}\mathrm{d}p)$$

自然我们就得出递推式。

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

当我们要计算连续的数的逆元时，我们可以采用以下递推式：$$inv(i)=(p-\lfloor \frac{p}{i}\rfloor )\times inv(p\mathrm{m}\mathrm{o}\mathrm{d}i)\mathrm{m}\mathrm{o}\mathrm{d}p$$

UPD@2019.10.9:补上这个式子的证明

证明：设$t=\lfloor \frac{p}{i}\rfloor ,k=p\mathrm{m}\mathrm{o}\mathrm{d}i$，那么显然有$$t\times i+k\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}p)$$

变形可得$$-t\times i\equiv k(\mathrm{m}\mathrm{o}\mathrm{d}p)$$

两边同时除以$ik$得到$$-t\times \frac{1}{k}\equiv \frac{1}{i}(\mathrm{m}\mathrm{o}\mathrm{d}p)$$

即$$inv(i)\equiv -t\times inv(k)(\mathrm{m}\mathrm{o}\mathrm{d}p)$$

所以有$$inv(i)=(p-\lfloor \frac{p}{i}\rfloor )\times inv(p\mathrm{m}\mathrm{o}\mathrm{d}i)\mathrm{m}\mathrm{o}\mathrm{d}p$$

乘法逆元的作用？

我们由费马小定理可得：$a\cdot a^{p-2}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}p)$。

所以： a p − 2 ≡ a − 1 ≡ 1 a ( m o d    p ) a^{p-2}\equiv a^{-1}\equiv\frac{1}{a}(\mod p) ap−2≡a