裴枢定理、扩展欧几里得算法及其证明
最编程
2024-07-18 22:05:54
...
定理
裴蜀定理（贝祖定理）是一个关于最大公约数的定理。
裴蜀定理说明了对任何整数a,b和它们的最大公约数d，关于未知数x和y的线性不定方程：若a,b是整数，且gcd(a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别的，一定存在整数x,y使ax+by=d成立。
重要推论
a、b互质的充分必要条件是存在整数x,y使ax+by=1。
证明
设d=gcd(a,b)，则d∣a,d∣b。由整除性质可得，
设s为ax+by的最小正值⋯⋯(1)
同理可证s∣b
证毕。
求不定方程的解
设d=gcd(a,b)
根据裴蜀定理可得到等式(贝祖等式):ax+by=d
即可发现x,y更新规律。
扩展欧几里得算法代码实现
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-y*(a/b);
return d;
}Q.E.D.