在数论中，裴蜀定理是一个关于最大公约数或者最大公约式的定理。
简介
裴蜀定理（或贝祖定理，Bézout’s identity）得名于法国数学家艾蒂安·裴蜀，说明了对任何整数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=
b1=(q2)(r1)+(r2),其中0=
(r1)=(q3)(r2)+(r3),其中0=
…..
(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。
以下证明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=
b1=(q2)(r1)+(r2),其中0=
(r1)=(q3)(r2)+(r3),其中0=
…..
(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。证法类似两个数的情况。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/204601.html原文链接：https://javaforall.net
