exgcd&二元一次丢番图方程

发表于 更新于

exgcd,二元一次丢番图方程

1.定理

对于任意整数\(a,b\)，存在一对整数\(x,y\),满足\(ax + by = gcd(a,b)\).

2.证明

1
2
3
4
5
int gcd(int a,int b) {
    if (b == 0)
        return a;
   	return gcd(b,a % b);
}

这是辗转相除法求gcd的代码。

我们可以发现当\(b = 0\)时，有一组\(x = 1,y = 0\)，使得\(ax + by = a \times 1 + b \times 0 = gcd(a,b) = a\)。

对于任意一组\(a,b\)，假设存在一对整数\(x,y\)使得\(bx + (a \% b)y = gcd(b,a \% b) = gcd(a,b)\)，对它变形： \[ bx + (a \% b)y = gcd(b,a \% b) = gcd(a,b)\\bx + (a - b \times \lfloor a / b \rfloor)y = gcd(a,b)\\ya + (x - y \times \lfloor a / b \rfloor)b = gcd(a,b) \] 所以我们有了一对\(x' = y,y' = x - y * \lfloor a / b \rfloor\)使得\(ax' + by' = gcd(a,b)\)。

3.代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<cstdio>

using namespace std;

int a,b,x,y,gcd;

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

int main() {
	scanf("%d%d",&a,&b);	
	gcd = exgcd(a,b,x,y);
	printf("%d %d\n",x,y);
	return 0;
}

4.求通解

上文中我们求出了一对\(x_0,y_0\)满足\(ax_0 + by_0 = gcd(a,b)\),现在来求通解。

取一组解\((x_1,y_1)\)，再任取一组解\((x_2,y_2)\)，有： \[ ax_1 + by_1 = ax_2 + by_2 = gcd(a,b)\\a(x_1 - x_2) = b(y_2 - y_1)\\两边同时除以gcd(a,b),设a / gcd(a,b) = a',b / gcd (a,b) = b'\\a'(x_1 - x_2) = b'(y_2 - y_1)\\此时gcd(a',b') = 1\\所以x_1 - x_2 = kb',y_2 - y_1 = ka' \]

5.另外一个定理

关于整数\(x,y\)的方程\(ax + by = c\)有解的充要条件是\(gcd(a,b)|c\)。