輾轉相除法(Algorithm of division)

在解決數學的難題上，為了因應複雜且時常遇到之問題，數學家研發出許多固定之算法或者公式，來幫助人民計算，而

此將先行介紹三大事件的時間發生。首先為歐基里德運用機械性的方式來求出最大公因數，而其機械式實質為一種偷工減

料的計算手段，利用一些制式化的步驟，而省略較繁複的手續，進而結合成機械化的模式，第二為艾爾法利茲米於應用問

題上的貢獻，他發明出現今看似平常的移項法，來幫助人們解決問題，最後則是進入電腦的計算上。而在此歷史演進中，

以下將特別介紹歐基里德的機械式方法，此即為輾轉相除法。

輾轉相除法中，主要針對兩者很大的數，其不易利用短除法來求初其公因數，因其研發出輾轉相除法之方式。首先將兩

者數字放於左右兩邊，並且於最左邊、兩數字之間以及最右邊，分別畫上三條直線，以做區隔，接著將較小的數於較大的

數底下在書寫一遍，並且相減的動作，因此其所得之結果，再與原本未經處理的較小的數做比較，求其最接近之倍數後，

則再乘上此倍數後一樣書寫於下方，並做相減的動作，接著則將其結果再與第一次相減之結果做比較，如此周而復始的操

作，直至有一邊相減後數字為0時，則可停止此操作，而可得到最大公因數即為另一邊的最後數字。透過上述講解，可了

解到輾轉相除法，即為於左右兩邊做相乘相減的動作，因此才有輾轉之名稱由來。(註1)

舉一例子做實際演練，如391與493，將此放於左右兩邊且畫上分隔線後，則開始進行操作，首先將391寫於493的下

方，相減後得到102的結果，此時將102與未經處理之391做比較，可知倍數為3時最接近且不超過，因此將

102X3=306寫於391下方，相減後得到85之結果，同樣85與102最接近為1倍之關係，因此直接將85書寫於102下

方，相減後得到17，此時再將17與85做比較，可知恰為5倍關係，而則將17X5=85書寫於85下方，因此相減後結果為

0，此時即可停止運算，得到最大公因數即為0旁邊之數字17。(註1)

中文關鍵字：輾轉相除法

英文關鍵字：Algorithm of division

註1 仲田紀夫/著。小學生數學大疑問，2001年初版，頁124~125。國際村文庫書店有限公司。

註2李嘉淦/著。中學數學科教材教法，1986年初版，頁232~233。千華出版公司。