Bezout定理内容以及它的应用,请高手帮帮忙!

Question

Bezout定理内容以及它的应用,请高手帮帮忙!

Answer 1

贝祖等式,依艾蒂·贝祖命名,是线性丢番图方程.
它说明若有整数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． (4)
在说明一般道理之前,先看下面的例子．
从求42897与18644的最大公约数出发：
42897=2×18644+5609,(i)
18644=3×5609+1817,(ii)
5609=3×1817+158,(iii)
1817=11×158+79,(iv)
158=2×79．
这样求出最大公约数是79．我们现在来寻求x、y,使
42897x+18644y=79．
由(iv)可知 1817-11×158=79．
把(iii)式的158表达式代入此式,得
79=1817-11(5609-3×1817)
=34×1817-11×5609．
再以(ii)式的1817表达式代入,得
79=34×(18644-3×5609)-11×5609
=34×18644-113×5609．
再以(i)式的5609表达式代入,得
79=34×18644-113×(42897-2×18644)
=260×18644-113×42897．
也就是x=-113,y=260．
这虽然是特例,也说明了一般的理论．一般的理论是：把辗转相除法写成为
a=a0b+r,
b=a1r+r1,
r=a2r1+r2,
r1=a3r2+r3,
………
r（n-1）=a（n+1）r（n）+ r（n+1）,
r（n）=a（n+2）r（n+1）．
这样得出最大公约数d=r（n+1）．由倒数第二式,r（n+1）可以表为r（n-1）、r（n）的一次式,再倒回一个可以表为r（n-2）、r（n-1）的一次式,…,最后表为a、b的一次式．
即把d放在等式的一边,另一边不断代入上一个等式,最后可找出一组（x、y）值,使 ax+by=d． 成立.
由此,贝式等式得证.
（结合上面的具体例子,自己代入再推导一下,就好理解了）