裴蜀定理

设\(gcd(a, b) = d\)，则对任意整数\(x, y\) 都有 \(d \mid ax + by\) 成立

特别地，一定存在\(x, y\) 满足 \(ax + by = d\)

等价的表述;不定方程\(ax + by = d\), \((a, b, d) \in Z\), 有解的充要条件为\(gcd(a, b) = d\)

推论: 当a, b 互质的时候等价于 \(ax + by = 1\)有解

证明

证明的话我们只需要求出解来，就证明了

那么现在如何求解？？

exgcd

令\(a = bq + r\)， 那么其中\(r = a \ mod \ b\)

递归求出\(bx + ry = d\)的解

设求出\(bx + ry = d\)的解为\(x = x_0, y = y_0\)， 考虑如何变形为\(ax + by = d\)的解

将 \(a= bq + r\) 带入\(ax+by = d\) 化简得\(b(xq+r)+rx= d\)

令\(xq+y = x_0, x=y_0\)上式成立，故\(x=y_0, y=x_0 - y_0q\)为\(ax+by=d\)的解

code

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