神马品牌网米线调味料品厂家:如何证明辗转相除法?
来源：百度文库 编辑：神马品牌网 时间：2024/04/30 02:39:03
设两数为x、y（不妨设x>y）
辗转相除法过程如下：
x=a(1)*y+b(1)
y=a(2)*b(1)+b(2)
b(1)=a(3)*b(2)+b(3)
b(2)=a(4)*b(3)+b(4)
.
.
.
b(n-2)=a(n)b(n-1)+b(n)
b(n-1)=a(n+1)b(n)+0
我们的目的是证明b(n)是x、y的最大公约数
由最后一个式子b(n-1)=a(n+1)b(n)我们很容易得到b(n-1)和b(n)的最大公约数是b(n)
把最后一个式子代入倒数第二个式子，我们可以得到：
b(n-2)=a(n)a(n+1)b(n)+b(n)
则b(n-2)和b(n)的最大公约数是b(n)
且a(n)和a(n)*a(n+1)+1互质，所以b(n)是b(n-2)和b(n-1)的最大公约数。
同理，依此类推，则可以得到b(n)是x、y的最大公约数
辗转相除法得证