数学之乘法逆元
Part1 : 逆元是什么
一个东西 的逆元，就是指在一种运算/操作下能够抵消这个东西所带来影响的东东
举个例子 4 的加法逆元 就是 -4
2 在普通乘法中的逆元就是 \(2^{-1}\)
而乘法逆元指的是在 模意义 下的乘法逆元
设原式为
\(1*a \equiv a \mod p\)
那么 \(a\) 的乘法逆元乘上去之后的效果就是
这里的 \(a^{-1}\) 指的是 \(a\) 的乘法逆元
\(1*a*a^{-1} \equiv 1 \mod p\)
即：
\(a*a^{-1} \equiv 1 \mod p\)
ps:知道了这些，以下的所有内容中的 \(xxx^{-1}\) 表示 \(xxx\) 的乘法逆元
Part2 ：有什么用
举个例子 要求出 $ \frac{a}{b} mod \ p$ 的值 ， 那该怎么算呢？
我们要知道的是，在模意义下，除以一个数等于乘以一个数的逆元
所以 \(\frac{a}{b} \bmod \ p =a*b^{-1} \bmod \ p\)
Part3 : 该怎么求
所以乘法逆元到底要怎么求呢？
有两种求法
Part3.1: 费马小定理
当 \(p\) 是质数时
\(a^{p-1} \equiv 1 \mod p\)
所以
\(a*a^{p-2} \equiv 1 \mod p\)
那么
\(a^{p-2}\)就是 \(a\) 的乘法逆元
这个可以用快速幂实现
Part3.2：扩展欧几里得算法
当 \(p\) 不是质数时，就要用到扩展欧几里得算法了
我太菜了，不会扩欧
那么要学会扩欧，先要学会 欧几里得定理 这个东西
至于为什么吗，因为要用到
欧几里得定理（辗转相除法）
\(gcd(a,b)=gcd(b,a\%b)\)
扩展欧几里得定理
我们有 \(a\) , \(b\)
现在要求出满足 \(ax + by =gcd(a,b)\) 的最小的 \(x\) 和其对应的 \(y\)
假如我们之前求出来了一组数 \(x_2,y_2\) 使得 \(bx_2 + (a \bmod b)y_2 = gcd(a,b)\)
那么 \(ax + by =bx_2 + (a \bmod b)y_2\) （3）
那当这个假如成立时怎么求呢？
取模运算的本质其实是 \(a \bmod b = a - b×\left \lfloor \frac{a}{b} \right \rfloor\)
所以 \(3\) 式本质上是
\(ax + by =bx_2 + (a - b×\left \lfloor \frac{a}{b} \right \rfloor)*y_2\) 继续推
\(ax + by =ay_2+bx_2 - b*\left \lfloor \frac{a}{b} \right \rfloor*y_2\)
\(ax + by =ay_2+b(x_2 - \left \lfloor \frac{a}{b} \right \rfloor*y_2)\)
那么，\(x,y\) 必然有一组解为 \(x=y_2,y=(x_2 - \left \lfloor \frac{a}{b} \right \rfloor*y_2)\)
所以，我们只用求出 \(x_2,y_2\) 就可以得出 \(x,y\) 了
那么，\(x_2,y_2\) 该怎么求b呢？
我们手上的要求的式子变为了
\(bx_2 + (a\bmod b)y_2 = gcd(a,b)\)
然后不断重复上面的求解过程，解出 \(x_2,y_2\)，但又要解出 \(x_3,y_3\)
这个过程中 \(x,y\) 的系数 \(s_x,s_y\) 不断被替换为 \(s_y,s_x\%s_y\)
直到最后，一定会出现 \(s_n=gcd(a,b),s_n=0\)
这个时候
方程长这样 \(s_xx_n+s_yy_n=gcd(a,b)\)
很明显的，当 \(x_n=1\) 时上式一定成立，这个时候 \(y_n\) 取任意值都可以，但建议取 0 免得神奇错误
然后不断回溯
好，你知道了这个，那么就可以继续了（我不会证）
我们先令 \(x=a^{-1}\)
所以
\(ax \equiv 1 \mod b\)
对于这个同余方程，我们将其变一下形式
\(ax + by = 1\)
其中 \(y\) 为一负数
标签：frac,gcd,欧几里得,逆元,ax,乘法,mod From： https://www.cnblogs.com/sea-and-sky/p/18381672