輾轉(zhuǎn)相除是什么

典型例題：
一.輾轉(zhuǎn)相除法
例1 。求兩個正數(shù)8251和6105的最大公因數(shù)。
（分析：輾轉(zhuǎn)相除→余數(shù)為零→得到結(jié)果）
解：8251＝6105×1＋2146
顯然8251與6105的最大公因數(shù)也必是2146的因數(shù)，同樣6105與2146的公因數(shù)也必是8251的因數(shù)，所以8251與6105的最大公因數(shù)也是6105與2146的最大公因數(shù)。
6105＝2146×2＋1813
2146＝1813×1＋333
1813＝333×5＋148
333＝148×2＋37
148＝37×4＋0
則37為8251與6105的最大公因數(shù)。
以上我們求最大公因數(shù)的方法就是輾轉(zhuǎn)相除法。也叫歐幾里德算法，它是由歐幾里德在公元前300年左右首先提出的。
1． 為什么用這個算法能得到兩個數(shù)的最大公因數(shù)？
利用輾轉(zhuǎn)相除法求最大公因數(shù)的步驟如下：
第一步：用較大的數(shù)m除以較小的數(shù)n得到一個商q0和一個余數(shù)r0；
第二步：若r0＝0，則n為m，n的最大公因數(shù)；若r0≠0，則用除數(shù)n除以余數(shù)r0得到一個商q1和一個余數(shù)r1；
第三步：若r1＝0，則r1為m，n的最大公因數(shù)；若r1≠0，則用除數(shù)r0除以余數(shù)r1得到一個商q2和一個余數(shù)r2；
……
依次計算直至rn＝0，此時所得到的rn－1即為所求的最大公因數(shù)

輾轉(zhuǎn)相除是為了求兩個數(shù)的公因數(shù)的，每次用兩個數(shù)中大的數(shù)減去小的數(shù)，得到的余數(shù)代替大的數(shù)成為新的數(shù)，直到兩數(shù)相等為止。舉個例子：
14和49 輾轉(zhuǎn)相除：
(1)49-14=35 用35代替49，兩數(shù)變?yōu)?4和35
(2)35-14=21 用21代替35，兩數(shù)變?yōu)?4和21
(3)21-14=7 用7代替21，兩數(shù)變?yōu)?4和7
(4)14-7=7 用7代替14，兩數(shù)變?yōu)?和7
兩數(shù)相等為7，所以最大公約數(shù)是7.