裴蜀(贝祖)定理
- 法国数学家艾蒂安·裴蜀,
- 对任何整数a、b和它们的最大公约数d
- 若a,b是整数,且gcd(a,b)=d,那么对于任意的整数x,y,ax+by都一定是d的倍数
- 一定存在整数x,y,使ax+by=d成立。
扩展欧几里得求解
- 裴蜀定理得ax1 + by1 = gcd(a,b) 和 bx2+(a%b)y2 = gcd(b,a%b)
- 欧几里得定理知:gcd(a,b) == gcd(b,a%b)。
- 因而ax1 + by1=bx2+(a%b)y2
- 模运算性质,有a%b = a - (a/b )* b
- 右边=bx2 + [ a - (a/b) * b] y2
- 即ax1 + by1==bx2 + [ a - (a/b) * b] y2=ay2 + b[ x2 - (a/b) y2];
- 由a、b系数相等的关系得到x1 = y2,y1 = x2 - a/b*y2
- 同理,将gcd(a%b,b%(a%b))进行求解,可得x2 = y3,y2 = x3 - a/b*y3
……
由展转相除法知,最后得到gcd(t,0)
- 即有txn + 0yn = gcd(t,0),则有xn=1,取yn=0,则为本方程的一组解。
- 再往上逆推xn-1 = yn,yn-1 = xn - a/b*yn,得到xn-1 = 0,yn-1 =1,最后可求出x1 和y1
递归代码
#include<iostream>
#include<cstring>
using namespace std;
int exgcd(int a,int b,int *x,int *y){
if(b==0){
*x=1;
*y=0;
return a;
}
int r=exgcd(b,a%b,x,y);
int t=*x;
*x=*y;
*y=t-a/b* *y;
return r;
}
int main(){
int x,y;
exgcd(97,127,&x,&y);
cout<<x<<","<<y<<endl;
return 0;
}