小鱼干

V1

2022/04/25阅读:16主题:橙心

贝祖等式与扩展欧几里得

定理

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

裴蜀定理说明了对任何整数a,b和它们的最大公约数d,关于未知数x和y的线性不定方程:若a,b是整数,且 ,那么对于任意的整数x,y,ax+by都一定是d的倍数,特别的,一定存在整数x,y使ax+by=d成立。

重要推论

a、b互质的充分必要条件是存在整数x,y使

证明

,则 。由整除性质可得, ,有

的最小正值

,则

,故r也为a,b的线性组合。

,故

同理可证

,且s是a与b的一个线性组合

证毕。

求不定方程的解

根据裴蜀定理可得到等式(贝祖等式):

,故

根据欧几里得算法,

,可得到一组特殊解:

,根据裴蜀定理:

即可发现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;
}

分类:

数学

标签:

数学编程

作者介绍

小鱼干
V1