輾轉相除法

歐幾里德 (Euclid 約前325 - 約前265)

(照片取自「The MacTutor History of Mathematics Achieve」http://www-gap.dcs.st-and.ac.uk/~history/ )

 

輾轉相除法 (Method of Successive Division) 又名歐幾里德算法 (Euclidean Algorithm) ,是一找尋兩數最大公因子 (G.C.D. Greatest Common Divisor) 的方法。

假設 a, b 為兩整數 (Integer),且 a > b。那麼根據除法算法 (Division Algorithm),我們可找到 q1 和 r1 使 a = q1b + r1,其中 0 < r1 < b。我們又可以找到 q2 和 r2 使 b = q2r1 + r2 ,其中 0 < r2 < r1。 這樣反覆的把兩數的餘數 (Remainder) 互除,輾轉相除法因而得名。最終到某一數整除另一數為止,那整除的數便是最大公因子。我們更可用代入法,計出 ax + by = (a,b) 的解 x, y 。

如求 105 和 234 的最大公因子:

因為 234 > 105 ,我們設 a = 234,b = 105,則有 234 = 2*105 + 24 ,我們又有 105 = 4*24 + 9 ,接下來 24 = 2*9 + 6,再來 9 = 1*6+3 ,最後 6 = 2*3,所以 (a,b) = 3。

那麼 (a,b) = 3 = 9 - 1*6,而 6 = 24 - 2*9,(a,b) = 9 - 1*( 24 - 2*9) = 3*9 - 24

而 9 = 105 - 4*24,所以 (a,b) = 3* (105 - 4*24) - 24 = 3*105 - 13*24,

而 24 = 234 - 2*105,所以最後 (a,b) = 3*105 - 13* (234 - 2* 105) = 31*105 - 13*234,

即 (x,y) = (31, -13)。

其實在計算型如 ax + by = c 的方程式時,輾轉相除法是相當重要的工具。