2023/04/裴蜀定理、扩展欧几里得及其证明

定理

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

裴蜀定理说明了对任何整数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\mid a,d\mid b$。由整除性质可得，$\forall x,y\in \mathbb{N}$,有$d\mid(ax+by)$。

设$s$为$ax+by$的最小正值$\cdots\cdots(1)$。

令 $a\ \div\ s=q\cdots r$，则$q=\lfloor \frac{a}{s}\rfloor$。

$r=a-q\cdot s=a-q\cdot(ax+by)=a-a\cdot qx-b\cdot qy$。

$r=a(1-qx)+b(-qy)$,故r也为a,b的线性组合。$\cdots\cdots(2)$

$\because r=a\ mod\ s$,故$0\leq r < s$。$\cdots\cdots(3)$

$\therefore (1)(2)(3) \Rightarrow r=0$

$\therefore a\div s=q$

$\therefore s\mid a$

同理可证$s|b$

$$\because \left\{\begin{aligned} s|a\\ s|b\\ d=gcd(a,b) \end{aligned}\right.$$

$\therefore d\ge s$

$\because d\mid a,d\mid b$,且s是a与b的一个线性组合

$\therefore d\mid s$

$\because d\mid s,s > 0$

$\therefore d\leq s$

$\because d\ge s,d\leq s$

$\therefore d=s$

$\therefore ax+by=d$

证毕。

求不定方程的解

设$d=gcd(a,b)$

根据裴蜀定理可得到等式(贝祖等式):$ax+by=d$

令$a\div b=\lfloor\frac{a}{b}\rfloor\cdots r$ ,故$r=a-\lfloor\frac{a}{b}\rfloor\cdot b$

根据欧几里得算法，$gcd(a,b)=gcd(b,a\%b)=gcd(b,r)=d$

当$b=0$，可得到一组特殊解：$x=1,y=0$

当$b\neq 0$，根据裴蜀定理：

$bx'+ry'=d$

$=bx'+(a-\lfloor\frac{a}{b}\rfloor\cdot b)y'=d$

$=bx'+ay'-b\cdot\lfloor\frac{a}{b}\rfloor y'=d$

$=ay'+b(x'-\lfloor\frac{a}{b}\rfloor y')=d$

$\because$

$$\left\{\begin{aligned} ay'+b(x'-\lfloor\frac{a}{b}\rfloor y')=d\\ ax+by=d \end{aligned}\right.$$

$\therefore$

$$\left\{\begin{aligned} x&=y' \\ y&=x'-\lfloor\frac{a}{b}\rfloor y' \end{aligned}\right.$$

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