贝祖等式的证明,具体的

贝祖等式的证明,具体的

问题补充说明：只要好,追加100分决不食言

注意：百度中无法显示数学中的脚标！a0,a1,...，a（n-1）,a（n）是数列，r1.r2,...,r（n-1）,r（n）也是数列。r（n-1）即数列的第(n-1)项别弄错了。得给百度提提意海布不血交形见了！

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

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

ax+by=d

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

例如12和42的最大公因子是6，便可以写(-直煤投培苦3)×12+1×42=6及4×360问答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．成立。

由此，贝式等式得证。

（结合上面的具体例子，自己代入再推导一下，就好理解了）