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$。