1.1.4 逆元

1.1.4 逆元主要内容：扩欧求逆元，快速幂求逆元，线性（递归）求逆元，同余模公式（补充），反复平方法求幂（补充）一、 逆元首先给出逆元的定义：$$\begin{aligned} 假设a\cdot p \equiv 1 \quad(mod \quad b)\\ 且(a,b)=1\quad即\quad a,b互素\\ 则称p为a的逆元，记作p=a^{-1} \end{aligned}$$用与前文类似的方法，我们将同余方程转化为二元一次不定方程：$$pa+qb=1$$则求解逆元的过程，就是对此不定方程求解的过程二、扩欧求逆元很明显，上面的方程是一个二元一次不定方程，我们可以使用扩欧求解具体代码参考1.1.3 最大公约数-CSDN博客即可三、快速幂求逆元快速幂求逆元运用费马小定理，这要求p为素数限于时间不足，作者将在之后的时间整理此部分内容四、 线性（递归）求逆元下面给出推导：$$\begin{aligned} 假设p=ki+r\\ 现在尝试求i在模p下的逆元i^{-1}，即有i\cdot i^{-1} \equiv 1\quad (mod\quad p)\\ 将上述等式放在模p意义下，得到同余式：\\ k\cdot i+ r\equiv0\quad(mod\quad p)\\ 两边同乘i^{-1}，得到\\ k+r\cdot i^{-1}\equiv 0\quad(mod\quad p)\\ 再同乘r^{-1}，得到\\ k\cdot r^{-1}+i^{-1}