裴蜀定理、扩展欧几里得算法及其证明

定理

裴蜀定理（贝祖定理）是一个关于最大公约数的定理。

裴蜀定理说明了对任何整数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.