LogoCSP Wiki By Yundou
0 MathBasics

裴蜀定理

定义

裴蜀定理,又称贝祖定理(Bézout's lemma)、贝祖等式(Bézout's identity)。是一个关于最大公约数的定理。

其内容是:

a,ba,b 是不全为零的整数,对任意整数 x,yx,y,满足 gcd(a,b)ax+by\gcd(a,b)\mid ax+by,且存在整数 x,yx,y, 使得 ax+by=gcd(a,b)ax+by=\gcd(a,b).

证明

对于第一点

由于 gcd(a,b)a,gcd(a,b)b\gcd(a,b)\mid a,\gcd(a,b)\mid b

所以 gcd(a,b)ax,gcd(a,b)by\gcd(a,b)\mid ax,\gcd(a,b)\mid by,其中 x,yx,y 均为整数

因此 gcd(a,b)ax+by\gcd(a,b)\mid ax+by

对于第二点

  1. 若任何一个等于 00, 则 gcd(a,b)=a\gcd(a,b)=a. 这时定理显然成立。

  2. a,ba,b 不等于 00.

    由于 gcd(a,b)=gcd(a,b)\gcd(a,b)=\gcd(a,-b),

    不妨设 a,ba,b 都大于 00ab,gcd(a,b)=da\geq b,\gcd(a,b)=d.

    ax+by=dax+by=d, 两边同时除以 dd, 可得 a1x+b1y=1a_1x+b_1y=1, 其中 (a1,b1)=1(a_1,b_1)=1.

    转证 a1x+b1y=1a_1x+b_1y=1.

    我们先回顾一下辗转相除法是怎么做的,由 gcd(a,b)gcd(b,amodb)\gcd(a, b) \rightarrow \gcd(b,a\mod b) \rightarrow \dots 我们把模出来的数据叫做 rr 于是,有

    gcd(a1,b1)=gcd(b1,r1)=gcd(r1,r2)==(rn1,rn)=1\gcd(a_1,b_1)=\gcd(b_1,r_1)=\gcd(r_1,r_2)=\cdots=(r_{n-1},r_n)=1

    把辗转相除法中的运算展开,做成带余数的除法,得

    a1=q1b1+r1(0r1<b1)b1=q2r1+r2(0r2<r1)r1=q3r2+r3(0r3<r2)rn3=qn1rn2+rn1rn2=qnrn1+rnrn1=qn+1rn\begin{aligned}a_1 &= q_1b_1+r_1 &(0\leq r_1<b_1) \\ b_1 &= q_2r_1+r_2 &(0\leq r_2<r_1) \\ r_1 &= q_3r_2+r_3 &(0\leq r_3<r_2) \\ &\cdots \\ r_{n-3} &= q_{n-1}r_{n-2}+r_{n-1} \\ r_{n-2} &= q_nr_{n-1}+r_n \\ r_{n-1} &= q_{n+1}r_n\end{aligned}

    不妨令辗转相除法在除到互质的时候退出则 rn=1r_n=1 所以有(qq 被换成了 xx,为了符合最终形式)

    rn2=xnrn1+1r_{n-2}=x_nr_{n-1}+1

    1=rn2xnrn11=r_{n-2}-x_nr_{n-1}

    由倒数第三个式子 rn1=rn3xn1rn2r_{n-1}=r_{n-3}-x_{n-1}r_{n-2} 代入上式,得

    1=(1+xnxn1)rn2xnrn31=(1+x_nx_{n-1})r_{n-2}-x_nr_{n-3}

    然后用同样的办法用它上面的等式逐个地消去 rn2,,r1r_{n-2},\cdots,r_1,

    可证得 1=a1x+b1y1=a_1x+b_1y. 这样等于是一般式中 d=1d=1 的情况。

推广

逆定理

a,ba, b 是不全为零的整数,若 d>0d > 0a,ba, b 的公因数,且存在整数 x,yx, y, 使得 ax+by=dax+by=d,则 d=gcd(a,b)d = \gcd(a, b)

特殊地,设 a,ba, b 是不全为零的整数,若存在整数 x,yx, y, 使得 ax+by=1ax+by=1,则 a,ba, b 互质。

多个整数

裴蜀定理可以推广到 nn 个整数的情形:设 a1,a2,,ana_1, a_2, \dots, a_n 是不全为零的整数,则存在整数 x1,x2,,xnx_1, x_2, \dots, x_n, 使得 a1x1+a2x2++anxn=gcd(a1,a2,,an)a_1 x_1 + a_2 x_2 + \cdots + a_n x_n=\gcd(a_1, a_2, \dots, a_n)。其逆定理也成立:设 a1,a2,,ana_1, a_2, \dots, a_n 是不全为零的整数,d>0d > 0a1,a2,,ana_1, a_2, \dots, a_n 的公因数,若存在整数 x1,x2,,xnx_1, x_2, \dots, x_n, 使得 a1x1+a2x2++anxn=da_1 x_1 + a_2 x_2 + \cdots + a_n x_n=d,则 d=gcd(a1,a2,,an)d = \gcd(a_1, a_2, \dots, a_n)

On this page