[笔记]模意义下的除法逆元

一些题目在涉及到超大整数运算时，往往会要求我们把答案取模一个值，比如\(998244353\)、\(10^9+7\)等等。如果我们的计算只有\(+,-,*\)，直接现算现取模即可：

(a + b) % mod = (a % mod + b % mod) % mod
(a - b) % mod = (a % mod - b % mod + mod) % mod
(a * b) % mod = (a * mod - b * mod) % mod

但如果遇到除法，我们就没法这么做了：
\(\frac{5}{3}*12\ mod\ 11=\ ?\)
\(\frac{10}{9}*81\ mod\ 13=\ ?\)
显然如果我们对分子和分母同时\(mod\ 11\)是没用的，还可能出现除不尽的情况。

所以我们思考：在模\(p\)意义之下，如果能把\(\frac{a}{b}*c\)转化成\(a*x*c\)，而取模结果不变就好了。

这个\(x\)即为乘法运算中，模\(p\)意义下，\(b\)的逆元。

换句话说，\(x\)就是模\(p\)意义下\(b\)的倒数（也可写作\(b^{-1}\)），所以有
\(b*x\equiv 1(mod\ p)\)
所以我们要求\(b^{-1}\)，其实就是求满足上面这个式子的\(x\)。

举例：

\(\frac{5}{3}*12\ mod\ 11=\ 9\\ 5*4*12\ mod\ 11=\ 9\)
（模\(3\)意义下\(3^{-1}=4\)）

\(\frac{10}{9}*81\ mod\ 13=\ 12\\ 10*3*81\ mod\ 13=\ 12\)
（模\(13\)意义下\(9^{-1}=12\)）

具体求法共有\(3\)种：

• 费马小定理
• 扩展欧几里得
• 线性递推

注意

• 模意义下除法逆元在\([0,p-1]\)范围内有一个，\([-p,-1],[p,2p-1],[2p,3p-1]\)等等都各有一个（举例：\(3*2\equiv 3*7\equiv 3*12\equiv …\equiv 1(mod\ 5)\)）。但我们为了方便使用，一般都定义逆元在\([0,p-1]\)范围内，是唯一存在的。
• 模\(p\)意义下\(a^{-1}\)存在的充分必要条件是\((a,p)=1\)，即\(a,p\)互质。
  所以，并不是\(p\)不为质数就没有逆元，也不是\(p\)为质数就一定存在逆元。
  证明

  若$(a,p)\neq 1$，$a^{-1}*a\equiv 1(mod\ p)$显然不成立。

费马小定理

定理内容：如果\(p\)是质数，则对于所有\((a,p)=1\)，有\(a^{p-1}\equiv 1(mod\ p)\)。
注：\((a,b)\)表示\(a,b\)的最大公因数。

转化一下，\(a^{p-2}*a\equiv 1(mod\ p)\)。
这个形式很熟悉？没错，\(a^{p-2}\ mod\ p\)就是模\(p\)意义下\(a\)的逆元。

使用快速幂来求，时间复杂度\(O(\log p)\)。

注意：仅限于\(p\)为质数。

扩展欧几里得

扩展欧几里得算法本质上是辗转相除法（欧几里得算法）的扩展，其内容是：对于两个整数\(a,b\)，必有\(x,y\)使得\(ax+by=(a,b)\)。

怎么与逆元挂钩呢？我们设模\(p\)意义下\(a^{-1}=x\)，那么有\(a*x\equiv 1(mod\ p)\)，即\(ax=py+1\)，由于\(y\)可正可负，我们可以\(ax+py=1\)。刚才提到了^ 模\(p\)意义下\(a^{-1}\)存在的充分必要条件是\((a,p)=1\)，所以其实\(ax+py=(a,p)\)。满足扩展欧几里得的条件。

由于这是一个不定方程，所以会有多个解，我们前面提到过用最小的非负\(x\)作为逆元（^ 为了方便使用，一般都定义逆元在\([0,p-1]\)范围内，是唯一存在的）。

接下来我们解这个不定方程：

• 根据辗转相除法，\((a,p)=(p,a\ mod\ p)\)。
• 故\(ax_1+py_1=px_2+(a\ mod\ p)y_2\)。
• \(ax_1+py_1=px_2+(a-\lfloor \frac{a}{p}\rfloor p)y_2\)。
• \(\textcolor{magenta}{ax_1}+py_1=px_2+\textcolor{magenta}{ay_2}-\lfloor \frac{a}{p}\rfloor p y_2\)
• 那么，满足下列条件：\(\begin{cases} x_1=y_2\\ y_1=x_2-\lfloor \frac{a}{p}\rfloor y_2 \end{cases}\)的情况下，如果\(x_2,y_2\)满足要求，那么\(x_1,y_1\)一样也满足要求。

所以，我们可以通过不断递归调用求出我们想要的\(x_1,x_2\)。每次递归提供a,b,&x,&y。后两个参数只是引用，用于在上一层把结果进行转换（就是用上面的结论，把下一层计算的\(x_2,y_2\)，变成这一层的\(x_1,y_1\)）。a和b分别对应上面结论中的\(a,p\)。

递归结束条件和辗转相除法一样：\(b=0\)。
此时的\(a\)就是我们所求的\(\gcd\)。
因为\(ax+by=\gcd\)，所以\(x=1,y=0\)，这就是递归边界。

最终求出的\(x,y\)称为这个不定方程的特解，我们可以通过这个特解求出这个不定方程的通解（无穷多个）。虽然不在模除逆元的范畴，但是有必要一提。

注：经过大量样例测试，发现求出的通解\(x,y\)是有取值范围的：$x∈[-⌊\frac{p}{2}⌋,⌊\frac{p}{2}⌋]，y∈[-⌊\frac{a}{2}⌋,⌊\frac{a}{2}⌋] $，但是还不会证明，如果观众们有思路欢迎在评论区讨论。

\(\textbf{[To be continuned...]}\)
\(\color{lightgray}\text{Next Dream...}\)

欢迎留下你的评论，我会认真阅读的！