輾轉相除法(I) (Euclidean algorithm)
輾轉相除法(I) (Euclidean algorithm)
國立蘭陽女中數學科陳敏晧老師
歷史溯源：歐幾里得(Euclid,ca.325BC-ca.265BC)(如右圖)的《幾何原本(Elements)》第七卷的第一、二個命題論述如何用輾轉相除法求兩整數的最大公因數，因此，輾轉相除法又稱歐幾里得算法。
狄里克利(Peter Gustav Lejeune Dirichlet, 1805-1859)在他的《數論》一書中說「本書的整個結構奠定在一塊基石上面，即計算兩個整數的最大公因數(輾轉相除法)。」利用這個方法，可以較快地求出兩個自然數的最大公因數，稱為 g.c.d.(greatest common divisior)[1]。 所謂最大公因數，是指幾個數的共有的因數之中最大的一個，例如：8和12的最大公因數是4，記作 g.c.d.(8,12)=4。