裴蜀定理

設\(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;
}