黃志鵬


【摘 要】 高中教材中出現了輾轉相除法,引發了我們對該算法的探究。文章先介紹最大公約數的一些基本性質和求法以及在解決實際問題中常見的應用,同時提出一些例子,方便讀者理解最大公約數,舉出幾個輾轉相除法在解題方面的應用,以此來加深讀者對輾轉相除法的理解。
【關鍵詞】 最大公約數;輾轉相除法
一、歷史來源
輾轉相除法是目前仍然在使用的歷史最悠久的算法之一。它首次出現于幾何原本(卷7命題1–2、卷10命題2–3)(大約公元前300年),而在中國則可以追溯至東漢出現的《九章算術》 。在卷7中用于整數,在卷10中用于線段的長度(也就是現在所說的實數,但是當時未有實數的概念)。卷10中出現的算法是幾何的,兩條線段a和b的最大公約數是準確測量a和b的最大長度。
二、簡介
在數學中,輾轉相除法又稱歐幾里得算法,是求最大公約數的算法。同時出現在高中教材人教A版必修三第一章第四節。在教學中,輾轉相除法是算法教學的經典案例,我們有必要加深教師對該案例的理解,加強對于學生對數學的深入學習,提高對數學學科的學習熱情。因此,我們很有必要對輾轉相除法的原理及應用進行探索。
三、最大公約數的應用
輾轉相除是后面才加入教材中的,是算法的經典案例,教學中注重這個內容的深入研究,是對于教學有促進作用的。放眼望去,輾轉相除法的應用極其廣泛,在各種計算機算法及編程中廣泛應用,特別地,在算法學習的研究中更是有著非常重要的地位。另外在高等數學中,它還被用來解丟番圖方程,尋找滿足中國剩余定理的數,或者求有限域中元素的逆。輾轉相除法還可以用來構造連分數,在施圖姆定理和一些整數分解算法中也有應用。輾轉相除法是現代數論中的基本工具。