扩展欧几里得 学习笔记

形式1：求方程\(ax+by=c\)的任意一组整数解。

形式2：求同余方程\(ax\equiv c\pmod b\)的最小整数解。

可以发现两种形式的问题可以互相转化。

辗转相除法求gcd

根据裴蜀定理，当且仅当\(gcd(a,b)|c\)时，原方程有整数解。

所以我们考虑解决方程\(ax+by=gcd(a,b)\)，最后同乘\(\frac{c}{gcd(a,b)}\)即可。

为方便描述，我们用\(\%\)代替\(\bmod\)。

有性质\(gcd(a,b)=gcd(b,a\%b)\)

我们假设已经解出方程\(bx'+(a\%b)y'=gcd(b,a\%b)\)，即\(bx'+(a\%b)y'=gcd(a,b)\)。

将\(a\%b\)展开，得\(bx'+(a-\lfloor \frac{a}{b}\rfloor\times b)y'=gcd(a,b)\)。

即\(ay'+b(x'-\lfloor \frac{a}{b}\rfloor y')=gcd(a,b)\)。

令\(x=y',y=x'-\lfloor \frac{a}{b}\rfloor y'\)，我们得到了原方程得一组解。

所以可以递归求解，终止条件是\(b=0\)，此时\(gcd(a,b)=a\)，方程组的解是\(x=1,y=0\)。

求\(x\)最小的解：

因为如果\((x,y)\)是一组解，则\((x+\frac{b}{gcd(a,b)},y-\frac{a}{gcd(a,b)})\)也是一组解，可以根据这个求出最小解。