辗转相除法

 指对两个正整数进行辗转相除而求得最大公约数的方法。它是一种普遍运用的方法，在解二元不定方程等问题中也有应用。
 作辗转相除法的基本要求和注意点是：①若两个正整数a与b,有a>b,则第一步应该用b对a作带余除法。得到a=bq₁+r₁后，若011与b作带余除法。②重复以上步骤时，都是用不为零的余数再对除数作带余除法，在每一步中余数都必须符合带余除法中的要求。
 对于一元多项式，亦有辗转相除法，它是求两个一元多项式的最大公因式的一种普遍适用的方法。其基本要求与注意点类似于两个正整数的辗转相除法(参见“带余除法”)。

辗转相除法zhanzhuan xiangchu fa

我国古代数学家创造的一种算法.但在外文书籍中通常把它叫做欧几里得算法.辗转相除法的具体做法如下：设a,b是任意两个正整数，由带余数除法定理，我们可得下列等式：

由于b>r₁>r₂>…，并且所有这些r_i都是非负整数，所以一定存在一个正整数n，使得r_n+1＝0
辗转相除法在求最大公因数，最小公倍数，解一次不定方程，解一次同余式以及求连分数展开式等都有重要应用.

辗转相除法Zhanzhuan xiangchufa

求两个数的最大公约数的一般方法。其步骤如下：设a和b是两个自然数，a>b, 先用b除a得商数q₃和余数r₁; 如果r₁≠0，那么r₁1除b，得商数q₂和余数_r2;如果r₂≠0，那么r₂1，再用r₂除r₁得商数q₃和余数r₃ ；……，如此继续下去，因为每一步所得的余数在逐步减小，所以经过有限步这样的除法后，必然得到一个余数r_k, 它整除前一个余数rk-₁。
a=bq₁+r₁,b=r₁q₂+r₂,r₁ = r2q3 +r3,
rk-2 =rk-1qk+rkrk-1 =rkqk+1,
那么，r_k也就是最后一个除数，就是a和b的最大公约数， 即rk= (a, b)。例： 求 (143, 221)。221÷143=1 (余78), 即221=143·1+78; 143÷78=1(余65)，即143=78·1+65;78÷65=1(余13)，即78=65·1+13; 65÷13=5(余0)，即65=13·5。那么， (143, 221) =13。

辗转相除法

一种带余除法。给定过程如下：整数a>0,b>0。可得到
　a=bq₁+r₁,01　b=r₁q₂+r₂,021
　r₁＝r₂q₃+r₃,032
　…　…
　r_n-2＝r_n-1q_n+r_n,0nn-1
　r_n-1＝r_nq_n+1+r_n+1,r_n+1＝0
即经过有限次除法，总可得到一个余数等于零。可用此法求最大公约数。对于给定的两个多项式f(x),g(x)，也可类似地利用辗转相除法求最大公因式。

辗转相除法

division algorithm