什麼是輾轉相除法?

Question

請問什麼是輾轉相除法.....?還有請舉ㄉ例子......謝謝~

Answer 1

輾轉相除法是用來求兩正整數的最大公因數的。通常是用在數字較大，且不易因數分解的時候。(但是，反過來說，數字小或是容易因數分解時，它也是適用的)
它是利用以下原理來求最大公因數：
若a,b,q為正整數，a≧b，0≦r≦b-1，且a=bq+r，
則(a,b)=(b,r)
a=bq+r用同餘式寫，亦可寫成a≡r(mod b)
因此我們可以利用這個原理，反覆地做除法，求出a,b的最大公因數，
餘數為0時的前一個餘數，即為最大公因數。
例如：
求91和20的最大公因數
91≡11(mod 20)
20≡9(mod 11)
11≡2(mod 9)
9≡1(mod 2)
2≡0(mod 1)
餘數分別是11,9,2,1,0，因此(91,20)=1

求90和34的最大公因數
90≡22(mod 34)
34≡12(mod 22)
22≡10(mod 12)
12≡2(mod 10)
10≡0(mod 2)
餘數分別是22,12,10,2,0，因此(90,34)=2
如果你要用電腦進行這個過程，可以用Excel寫，請在C1儲存格輸入「=MOD(A1,B1)」，然後D1、E1、F1、G1、H1、I1、J1、K1、L1都複製C1再貼上(應該夠用了....)，然後A1和B1再輸入你想求最大公因數的兩個數(誰大誰小沒關係)，這樣一整列應該會出現例如這樣的東西
91....20.....11.....9....2....1....0....#DIV/0!....#DIV/0!
0的右邊應該是一連串的"#DIV/0!"(註)，而0的左邊一個數就是最大公因數啦！

註：這是Excel的某個程式輸入錯誤提示，如果你的除數是0或空白，就會出現這個東西。

Answer 2

簡單說121比11
=先用121-11的X倍(看最多可以多少)
如果整剛好-完
旁邊那個數(X倍)=最大公因數

Answer 3

 在初等數論中，求兩正整數的最大公因數有兩 種方法。第一種就是因數分解法，亦即分別先將兩 數分解成質數的羃次的乘積，則其共同質因數羃次的乘積即為所求；第二種就是所謂輾轉相除法，具 體來說，它的演算法則是 定理1.[輾轉相除法演算法則]設a0,a1是兩個給定的正整數，若a1 不能整除a0，則反覆應用帶餘數的除法可得到下面k個等式：                      a0=q0a1+a2, 0 < a2< a1                      a1=q1a2+a3, 0 < a3< a2                      a2=q2a3+a4, 0 < a4< a3                        ……      ……                      an-2=qn-2an-1+an, 0 >第七卷中提出，而它的演算法則涵蓋了 下列兩個問題 1.首先，輾轉相除法的演算步驟為何只需有限個步    驟即可完成？ 2.第二，輾轉相除法演算所需時間是否''合理''，亦即   ：對於兩個正整數，利用輾相除法求其最大公因數    所花費時間是否需要''幾天''、甚至''幾年''。本文目的是要利用兩個深刻的數學思想，回答上述問題。