bezout定理的内容

贝祖等式，依艾蒂·贝祖命名，是线性丢番图方程。

它说明若有整数a、b和其最大公因子d，必存在整数x、y使得：

ax + by = d

x、y称为贝祖数，可用扩展版辗转相除法求得，但结果不是唯一的。

例如12和42的最大公因子是6，便可以写(-3)×12 + 1×42 = 6及4×12 + (-1)×42 = 6。

d其实就是最小可以写成ax + by形式的正整数。

辗转相除法是用来求最大公约数的．我们用代数的形式来表达(实质上，算术形式也是可以完全讲得清楚的)．给出两个正整数a和b，用b除a得商a0，余数r，写成式子

a=a0b+r，0≤r＜b． (1)

这是最基本的式子，辗转相除法的灵魂．如果r等于0，那么b可以除尽a，而a、b的最大公约数就是b．

如果r≠0，再用r除b，得商a1，余数r1，即

b=a1r+r1，0≤r1＜r．

(2)如果r1=0，那么r除尽b，由(1)也除尽a，所以r是a、b的公约数．反之，任何一龀、b的数，由(1)，也除尽r，因此r是a、b的最大公约数．

如果r1≠0，则用r1除r得商a2，余数r2，即

r=a2r1+r2，0≤r2＜r1． (3)

如果r2=0，那么由(2)可知r1是b、r的公约数，由(1)，r1也是a、b的公约数．反之，如果一数除得尽a、b，那末由(1)，它一定也除得尽b、r，由(2)，它一定除得尽r、r1，所以r1是a、b的最大公约数．

如果r2≠0，再用r2除r1，如法进行．由于b＞r＞r1＞r2＞…逐步小下来，而又都是正整数，因此经过有限步骤后一定可以找到a、b的最大公约数d(它可能是1)．这就是有名的辗转相除法，在外国称为欧几里得算法．这个方法不但给出了求最大公约数的方法，而且帮助我们找出x、y，使

ax+by=d．