裴蜀定理

简介在数论中，裴蜀定理是一个关于最大公约数（或最大公约式）的定理。裴蜀定理得名于法国数学家艾蒂安·裴蜀，说明了对任何整数a、b和它们的最大公约数d，关于未知数x和y的线性丢番图方程（称为裴蜀等式）：若a,b是整数,且(a,b)=d,那么对于任意的整数x,y,ax+by都一定是d的倍数,特别地,一定存在整数x,y,使ax+by=d成立。

它的一个重要推论是：a,b互质的充要条件是存在整数x,y使ax+by=1.

证明如果 a 和 b 有一个是0，那么它们两个的最大公约数是0。这时定理显然成立。

以下证明a和b都不等于0的情况。不妨设a,b都大于零，a>=b.设(a,b)=d

对ax+by=d，两边同时除以d，可得(a1)x+(b1)y=1，其中(a1,b1)=1。

转证(a1)x+(b1)y=1。由带余除法：

a1=(q1)b+(r1),其中0=<r1<b1

b1=(q2)(r1)+(r2),其中0=<r2<r1

(r1)=(q3)(r2)+(r3),其中0=<r3<r2

.....

(rn-3)=(qn-1)(rn-2)+(rn-1)

(rn-2)=(qn)(rn-1)+(rn)

(rn-1)=(qn+1)(rn)

于是，有(a1,b1)=(b1,r1)=(r1,r2)=...=(rn-1,rn)=1

故

(rn-2)=(xn)(rn-1)+1

即1=(rn-2)-(xn)(rn-1)

由倒数第三个式子（rn-1）=(rn-3)-(xn-1)(rn-2)代入上式，得

1=[1+(xn)(xn-1)](rn-2)-(xn)(rn-3)

然后用同样的办法用它上面的等式逐个地消去(rn-2),...(r1),

可证得1=(a1)x+(b1)y。

n个整数间的裴蜀定理设a1,a2,a3......an为n个整数，d是它们的最大公约数，那么存在整数x1......xn使得x1*a1+x2*a2+...xn*an=d。

特别来说，如果a1...an互质(不是两两互质），那么存在整数x1......xn使得x1*a1+x2*a2+...xn*an=1。

任意主理想环上的情况裴蜀可以推广到任意的主理想环上。设环A是主理想环，a和b 为环中元素，d是它们的一个最大公约元，那么存在环中元素x和y使得：

ax + by = d

这是因为在主理想环中，a和b的最大公约元被定义为理想aA + bA的生成元。