首页 > 代码库 > 裴蜀定理

裴蜀定理

最大公约数:d = gcd(a,b)


裴蜀定理:存在u,v使得a*u + b*v = d


裴蜀定理特例:若a,b互质,gcd(a,b) = 1则存在u,v 使得a*u + b*v = 1


设 a = pd, b = qd, 则p,q互质(为什么?)

裴蜀定理  pdu + qdv = d ->pu + qv = 1

证明:

直接构造出u,v
au + bv = d
(a-b)u + b(u+v) = d
令a’ = a%b,     令t使得a = b*t + a’
t = (a-a’)/b
(a-tb)u + b(tu + v) = d
a’u + b(tu+v) = d
令v’ = tu+v, 得到a’u + bv’ = d

v = v’ – tu 若知道(u, v’)则可知道(u,v)

代码实现:

int gcd(int a, int b){
	return b==0?a:gcd(b,a%b);
}
int ex_gcd(int a,int b, int &u, int &v){
	If (b == 0){
		u = 1, v = 0;
		Return a;
	}
	int d = ex_gcd(b, a%b, v, u);//反转
	v = v - a/b *u;              //容易溢出
	return d;
}
看完了,觉得用处不是很大,找了一道题看了下,作为应用参考吧。

链接:http://blog.csdn.net/acdreamers/article/details/12347475

裴蜀定理