請問展轉相除法是如何計算?

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

舉例:比如說你要找210跟25的最大公因數可以寫成
8| 210| 25|2 就先拿小的乘以多少倍可以跟大的差最接近...然後先減
| 200| 20| 餘數寫在另一條線下面..然後拿餘數乘多少倍..可以跟
------------- 最小的差最近..在減掉它....之後於數寫到下面...這樣當
2|10 | 5| 做一倫...然後把剩下來的那兩個餘數當作..一開始的照
10 這樣做下去..當減掉後變成0時..。哪之前拿來乘的就是
------------ 一開始兩數的最大公因數......那為什麼要寫出乘幾次呢
0 ???因為以後還要教一下往回推的東西..所以養成習慣
比較好...^^