贝祖等式的证明,具体的

贝祖等式的证明,具体的

注意：百度中无法显示数学中的脚标！ 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×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． 成立。由此，贝式等式得证。（结合上面的具体例子，自己代入再推导一下，就好理解了）