作者：國立台灣師範大學數學系教授 許志農

 

如果我們將一則數學問題的證明或解答中的邏輯推理及語文給剔除，所剩下的部份不是數學公式就是數學演算法。所謂數學公式是指所要求的值可以用一個公式給表達出來，例如三角形的面積公式、一元二次方程式的根的公式解、餘弦定理、正弦定理等。但並不是所有所要求的值都可以用一個公式給表示出來，例如求最大公因數就不能用一個公式來表示，而只能根據歐基里得輾轉相除法的過程來求兩數的最大公因數（或者將兩數個別作因數分解，求它們最大的共同因數）。像這樣的方法就叫做數學演算法。另兩個耳熟能詳的數學演算法就是判別一個正整數是否為質數的方法及第3 節的一次因式檢驗法。我們習慣稱前種方法為埃拉托塞尼篩法（一種篩選質數的方法）。因為演算法是比數學公式較有深度的數學方法，所以歐基里得的輾轉相除法與埃拉托塞尼篩法是歷史上很早且很有名的兩則數學演算法。本節的目的就是要介紹歐基里得的輾轉相除法。