不定方程

裴蜀定理

给定参数 $a,b$ 。

$x,y$ 作为未知数，$ax+by=m$ 有解的充分必要条件是 $gcd(a,b)|m$。

证明：

设 $S$ 集合是 $ax+by$ 的取值集合。

其中 $g$ 是 $S$ 中的最小正整数。

设$a{x}_0+b{y}_0=g$

因为 $gcd(a,b)|ax$ 且 $gcd(a,b)|by$ ，所以 $gcd(a,b)|g$。（1）

设 $a=k\ast g+r(0\le r<g)$ ，$r=amodg$。

则 $r=a-k\ast g=a-k(a{x}_0+b{y}_0)=a(1-k{x}_0)+b(-y_0)$。

设 $x_1=1-k{x}_0,y_1=-y_0$，则 $r=a{x}_1+b{y}_1$。

所以 $r\in S$，且 $r\ne g$。

因为 $g$ 是最小正整数，所以 $r=0$。

所以 $a=k\ast g$，得出 $g|a$。

同理可得：$g|b$。

综上：$g|gcd(a,b)$。（2）

根据（1）（2）得出，$g=gcd(a,b)$。

所以得出最小正整数是 $gcd(a,b)$。

而 $ax+by=m$ 不可能得到 $gcd(a,b)$ 倍数以外的数值，有解的充分必要条件是 $gcd(a,b)|m$。

P4549 【模板】裴蜀定理

扩展欧几里得

知道 $ax+by=m$ 有解的条件后，还需要求出一对 $x,y$ 的值。

可以先求出 $ax+by=gcd(a,b)$ 的值，然后再将 $x,y$ 乘以 $\frac{m}{gcd(a,b)}$ 倍。

考虑欧几里得算法，有 $gcd(a,b)=gcd(b,a\mathrm{\%}b)$。

设 $a{x}_1+b{y}_1=b{x}_0+(a\mathrm{\%}b)y_0=gcd(a,b)$

我们知道欧几里得算法迭代到最后会变成 $(gcd,0)$ 的，此时只要赋值 $x=1,y=0$ 就可以得到 $gcd\ast 1+0\ast 0=gcd$。

所以我们相当于知道了 $x_0,y_0$ ，想要求出 $x_1,y_1$。

$a\mathrm{\%}b=a-\lfloor \frac{a}{b}\rfloor \ast b$

$b{x}_0+(a\mathrm{\%}b)y_0=b{x}_0+(a-\lfloor \frac{a}{b}\rfloor \ast b)y_0=a{y}_0+b(x_0-\lfloor \frac{a}{b}\rfloor y_0)$。

$x_1=y_0$ ，$y_1=x_0-\lfloor \frac{a}{b}\rfloor y_0$ 。

int exgcd(int a,int b,int &x,int &y)
{
	if(b==0){x=1,y=0;return a;}
    int g=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return g; 
}

这样可以得到 $ax+by=gcd$ 的其中一组解（$x_0,y_0$）。

显然作为二元二次不定方程，它不只有一组解。

设 $a(x+t_1)+b(y-t_2)=ax+by$

移项 $a{t}_1=b{t}_2$。

求最小的 $t_1,t_2$ ，可以让两边都等于 $lcm(a,b)$，得出 $t_1=\frac{b}{gcd(a,b)},t_2=\frac{a}{gcd(a,b)}$。

所以，$ax+by=gcd$ 的通解是 $x=x_0+k\ast \frac{b}{gcd(a,b)},y=y_0-k\ast \frac{a}{gcd(a,b)}$。

练习题

P5656 【模板】二元一次不定方程 (exgcd)

P1516 青蛙的约会

P1082 [NOIP2012 提高组] 同余方程

P2421 [NOI2002] 荒岛野人