黃志鵬

【摘 要】 高中教材中出現(xiàn)了輾轉(zhuǎn)相除法，引發(fā)了我們對(duì)該算法的探究。文章先介紹最大公約數(shù)的一些基本性質(zhì)和求法以及在解決實(shí)際問題中常見的應(yīng)用，同時(shí)提出一些例子，方便讀者理解最大公約數(shù)，舉出幾個(gè)輾轉(zhuǎn)相除法在解題方面的應(yīng)用，以此來加深讀者對(duì)輾轉(zhuǎn)相除法的理解。

【關(guān)鍵詞】 最大公約數(shù);輾轉(zhuǎn)相除法

一、歷史來源

輾轉(zhuǎn)相除法是目前仍然在使用的歷史最悠久的算法之一。它首次出現(xiàn)于幾何原本（卷7命題1–2、卷10命題2–3）（大約公元前300年），而在中國則可以追溯至東漢出現(xiàn)的《九章算術(shù)》 。在卷7中用于整數(shù)，在卷10中用于線段的長度（也就是現(xiàn)在所說的實(shí)數(shù)，但是當(dāng)時(shí)未有實(shí)數(shù)的概念）。卷10中出現(xiàn)的算法是幾何的，兩條線段a和b的最大公約數(shù)是準(zhǔn)確測(cè)量a和b的最大長度。

二、簡介

在數(shù)學(xué)中，輾轉(zhuǎn)相除法又稱歐幾里得算法，是求最大公約數(shù)的算法。同時(shí)出現(xiàn)在高中教材人教A版必修三第一章第四節(jié)。在教學(xué)中，輾轉(zhuǎn)相除法是算法教學(xué)的經(jīng)典案例，我們有必要加深教師對(duì)該案例的理解，加強(qiáng)對(duì)于學(xué)生對(duì)數(shù)學(xué)的深入學(xué)習(xí)，提高對(duì)數(shù)學(xué)學(xué)科的學(xué)習(xí)熱情。因此，我們很有必要對(duì)輾轉(zhuǎn)相除法的原理及應(yīng)用進(jìn)行探索。

三、最大公約數(shù)的應(yīng)用

輾轉(zhuǎn)相除是后面才加入教材中的，是算法的經(jīng)典案例，教學(xué)中注重這個(gè)內(nèi)容的深入研究，是對(duì)于教學(xué)有促進(jìn)作用的。放眼望去，輾轉(zhuǎn)相除法的應(yīng)用極其廣泛，在各種計(jì)算機(jī)算法及編程中廣泛應(yīng)用，特別地，在算法學(xué)習(xí)的研究中更是有著非常重要的地位。另外在高等數(shù)學(xué)中，它還被用來解丟番圖方程，尋找滿足中國剩余定理的數(shù)，或者求有限域中元素的逆。輾轉(zhuǎn)相除法還可以用來構(gòu)造連分?jǐn)?shù)，在施圖姆定理和一些整數(shù)分解算法中也有應(yīng)用。輾轉(zhuǎn)相除法是現(xiàn)代數(shù)論中的基本工具。