定理

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

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

重要推论

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

证明

d=gcd(a,b)d=gcd(a,b),则da,dbd\mid a,d\mid b。由整除性质可得,x,yN\forall x,y\in \mathbb{N},有d(ax+by)d\mid(ax+by)

ssax+byax+by的最小正值(1)\cdots\cdots(1)

a ÷ s=qra\ \div\ s=q\cdots r,则q=asq=\lfloor \frac{a}{s}\rfloor

r=aqs=aq(ax+by)=aaqxbqyr=a-q\cdot s=a-q\cdot(ax+by)=a-a\cdot qx-b\cdot qy

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

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

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

a÷s=q\therefore a\div s=q

sa\therefore s\mid a

同理可证sbs|b

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

ds\therefore d\ge s

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

ds\therefore d\mid s

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

ds\therefore d\leq s

ds,ds\because d\ge s,d\leq s

d=s\therefore d=s

ax+by=d\therefore ax+by=d

证毕。

求不定方程的解

d=gcd(a,b)d=gcd(a,b)

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

a÷b=abra\div b=\lfloor\frac{a}{b}\rfloor\cdots r ,故r=aabbr=a-\lfloor\frac{a}{b}\rfloor\cdot b

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

b=0b=0,可得到一组特殊解:x=1,y=0x=1,y=0

b0b\neq 0,根据裴蜀定理:

bx+ry=dbx'+ry'=d

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

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

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

\because

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

\therefore

{x=yy=xaby\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;
}

Q.E.D.


( ノ^ω^)ノ゚ 稻 花 香 里 说 丰 年 , 听 取 WA 声 一 片 。(╥╯^╰╥)