乘法逆元

定义

如果$ab\equiv1 (\mod p)$,则称b为a关于1 $\%$p的逆元，计b为inv(a).

用处

在写代码时，很容易遇到要求$\frac{a}{b}\%p$的情况，这样一般求起来很绝望，因为很多人喜欢每个数都模p，这样在加减乘中都是可行的，但是在除中确实不可行的，所以这种情况下我们就要用到乘法逆元。很容易发现，a关于1模p的逆元就是a在模p意义下的倒数，所以$\frac{a}{b}\%p=a \times inv(b)$

前置知识列表

欧拉定理

$a^{\varphi(n)}\equiv 1 (\mod n)$

$\varphi(n)$表示小于n中与n互质的数；

证明：
设小于n中与n互质的数为$x_1,x_2,x_3……x_{\varphi(n)}$,将其中的每一个数都乘以a(a与n互质)，得到一个新的数列：{$ax_1,ax_2,……ax_{\varphi(n)}$,},我们将新数列中的每一项模n，可已得到原数列完全相同的数列。既对于任何数

$x_i \equiv ax_i(\mod n)$,换而言之，新数列中的每一个数模n没有重复。因为a与n互质，任意$x_i$与n也互质，所以有gcd(n,$axi$)=1,根据欧几里得定理，得到gcd(n,$ax_i\% $),n所以任意一个新数列中的数都与n互质。同时，他们也无重复，用反证法来证明，若$ax_1\%n=ax_2\%n$,则有，$n|(ax1-ax2)$,因为a与n互质且(x1-x2)小于n,所以等式不成立，故有新数列无重复元素。

那么我们将两个式子合并一下，$\coprod\limits_{i=1}^{\varphi(n)}ax_i\equiv \coprod\limits_{i=1}^{\varphi(n)}x_i$ ($\mod p$)

化简：$a^{\varphi(n)}\equiv\ 1 (mod\ n)$

费马小定理

对于任何数a 和质数 p ,$a^{p-1}\equiv 1 \ (mod\ p)$

这个真的没什么好讲的，其实就是欧拉定理的一个特殊情况，由于p是个质数，那么$\varphi(p)=p-1$,根据欧拉定理，$a^{\varphi(p)}\equiv 1 (\mod p)$，所以成立(还是想吐槽一句，费马你是捡漏了吗？)

欧拉定理拓展

$a^{b}\equiv\ a^{b \mod \varphi(n)}\ (mod \ n)$

证明：
$a^{b-b \mod \varphi(n)}\times a^{b \mod \varphi(n)}\ \equiv\ a^{b \mod \varphi(n)}\ (mod \ n)$

$a^{b-b \mod \varphi(n)}\equiv 1 (\mod n )$

因为$b-b\mod \varphi(n)| \varphi(n)$

设$b-b \mod \varphi(n)=k\varphi(n)$

原式变为$a^{k\varphi(n)}\equiv 1 (\mod n)$

$(a^k)^{\varphi(n)}\equiv 1(\mod n)$

因为a与n互质，$a^k$与n也互质，

根据欧拉定理，原式成立。

拓展欧几里得定理

$ax1 + by1=gcd(a,b)$

$bx2 + (a\%b)y2=gcd(b,a\%b)$

$ax1+ by1=bx2+ [a-a/b*b]y2$

$ax+ by1=bx2 + ay2-\frac{a}{b}\ y2 \times b$

$ax1 \times by1 =ay2 \times b(x2-a/by2)$

既x1=y2,y1=x2-a/b*y2

乘法逆元的计算

费马小定理求逆元

根据费小定理，我们可以将原式子化为$a \times a^{n-2}\equiv 1(\mod n)$

也就是我们可以用快速幂求出$a^{n-2}$,就可以了。

但是这样当多次调用逆元时不排除去世的可能。