扩展欧几里得

扩展欧几里得用于求解形如 $ax+by=m$ 的不定方程，也常用于求逆元。

裴蜀定理

对于任意整数 $a,b$，方程

$$ax+by=m$$

有整数解的充要条件是：

$$\gcd(a,b) \mid m$$

因此可以先求出 $ax+by=\gcd(a,b)$ 的一组解，再按比例扩展到一般的 $m$。

递归推导

因为：

$$\gcd(a,b)=\gcd(b,a\bmod b)$$

假设递归下一层已经求出：

$$bx_2+(a\bmod b)y_2=\gcd(a,b)$$

又因为：

$$a\bmod b=a-\left\lfloor \frac{a}{b}\right\rfloor b$$

代入可得：

$$bx_2+\left(a-\left\lfloor \frac{a}{b}\right\rfloor b\right)y_2=\gcd(a,b)$$

整理系数：

$$ay_2+b\left(x_2-\left\lfloor \frac{a}{b}\right\rfloor y_2\right)=\gcd(a,b)$$

所以当前层的一组解为：

$$x_1=y_2, \quad y_1=x_2-\left\lfloor \frac{a}{b}\right\rfloor y_2$$

递归终点是 $b=0$，此时：

$$a\cdot 1+b\cdot 0=a$$

从终点向上回代，就能得到最终的 $x,y$。

求逆元

若要求 $a$ 在模 $m$ 意义下的逆元，即：

$$ax \equiv 1 \pmod m$$

可以转化为：

$$ax+my=1$$

只要 $\gcd(a,m)=1$，就可以用扩展欧几里得求出 $x$，再把 $x$ 调整到 $[0,m)$ 范围内即可。