拓欧求逆元

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16531857.html

相关文章：

• 拓展欧几里得小结 内容基本一样
• 一本通提高篇之同余问题（课堂笔记）有些例题
• 其他 博客相关文章

这篇文章内容之前已经记过一次了，但用的时候又忘了，再记一下

之前的这篇会详细很多

拓展欧几里得复习

$$\Large ax+by=\gcd(a,b)$$

其中 $a,b$ 已知，求 $x,y$

正常的推导应该都会，拆开后合并同类项最终化为：

$$\Large ay'+b(x'-\frac a by')=\gcd(b,a\bmod b)$$

所以 $x=y', y=\dfrac a b y'$，代码实现时我们是知道当前这一步的 $x',y'$，要推回上一步的 $x,y$，直接套上面式子

边界条件和打普通gcd一样，若 $b=0$ 就结束，此时 $x=1,y=0$

拓欧求逆元

前提：$\gcd(a,p)=1$

求 $a$ 在模 $p$ 意义下的逆元，可以表示为求 $ax\equiv 1\pmod p$ 中的 $x$

怎么用拓欧做？回到拓欧式子：

$$\Large ax+by=\gcd(a,b)$$

已知的是 $a,p$，直接套进去：

$$\Large ax+py=\gcd(a,p)$$

$\gcd(a,p)$ 已知为1：

$$\Large ax+py=1$$

那模 $p$ 后必然相同，即：

$$\Large ax+py\equiv 1\pmod p$$

约去 $py$：

$$\Large ax\equiv 1\pmod b$$

$x$ 就是答案