福建省福州第七中學(xué) 黃志鵬

一、歷史來源

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

二、簡(jiǎn)介

在數(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)用

1.最大公約數(shù)的定義

整數(shù)a1，a2，a3，…，an的公因數(shù)中最大的一個(gè)叫作最大公約數(shù)，記作（a1，a2，a3，…，an），若（a1，a2，a3，…，an）=1，我們則說a1，a2，a3，…，an互質(zhì)或互素。

2.最大公約數(shù)的求解方法

例1：求20、30 和36 的最大公約數(shù)。解法一： 列舉法。

20 的因數(shù)有：1、2、4、5、10、20。

30 的因數(shù)有：1、2、3、5、6、10、15、30。

36 的因數(shù)有：1、2、3、4、6、9、12、18、36。

三個(gè)數(shù)的最大公約數(shù)是2。解法二：分解質(zhì)因數(shù)的方法。

20=2×2×5，

30=2×5×3，

36=2×2×3×3，

（20，30，36）=2。解法三：短除的方法

（20，30，36）=2。

小結(jié)：在計(jì)算三個(gè)數(shù)的最大公約數(shù)的時(shí)候，要找三個(gè)數(shù)的公有的質(zhì)因數(shù)，如果其中的兩個(gè)商還有質(zhì)因數(shù)，也不要往下除。

例2：求18 和24 的最大公約數(shù)。

解：（1）用分解質(zhì)因數(shù)的方法獨(dú)立完成。

（18，24）=2×3=6。

[18，24]=2×3×3×2×2=72。

（2）觀察發(fā)現(xiàn)：18×24=4×72。

小結(jié)：兩個(gè)自然數(shù)的最大公約數(shù)的一個(gè)重要性質(zhì)是：兩個(gè)自然數(shù)的乘積等于這兩個(gè)自然數(shù)的最大公約數(shù)和最小公倍數(shù)的乘積。

延伸：若a、b 表示兩個(gè)自然數(shù)，則 a×b=（a，b）×[a，b]。

例3：兩個(gè)數(shù)的最大公約數(shù)是6，最小公倍數(shù)是504，如果其中的一個(gè)數(shù)是42，那么另一個(gè)數(shù)是多少？

3.利用最大公因數(shù)解決實(shí)際問題

例4：有320 個(gè)蘋果，240 個(gè)橘子，200 個(gè)梨。用這些果品，最多可以分成多少份同樣的物？在每份禮物中，蘋果、橘子和梨各有多少個(gè)？

分析：根據(jù)題目的要求，在分禮物的時(shí)候必須正好分盡3 樣果品。因此，禮物的份數(shù)必須是320、240 和200 的公因數(shù)，現(xiàn)在還要求最多可以分成多少份同樣的禮物，也就是說要求320、240 和200 的最大公因數(shù)。

解：用短除法：

（320，240，200）=2×2×2×5=40。

因此，最多可以分成40 份，每份禮物中有蘋果320÷40=8（個(gè)），橘子240÷40=6（個(gè)），梨200÷40=5（個(gè)）。

四、輾轉(zhuǎn)相除法在解題中的應(yīng)用

1.兩個(gè)有理數(shù)公因數(shù)的求法

2.兩個(gè)無理數(shù)公因數(shù)的求法

其中，a 為任意實(shí)數(shù)，甚至可以是多項(xiàng)式。

4.運(yùn)用輾轉(zhuǎn)相除法把最大公約數(shù)表示為某量整數(shù)的倍數(shù)和

定理：若（a，b）=d，則必有二整數(shù)k、l 使得d=ka+lb。

例7：求一組整數(shù)x、y，使得150x+42y=（150，42）。

解：我們可以將輾轉(zhuǎn)相除過程寫成橫式(主要是在于應(yīng)用歐拉演段)：

得到6 為150 和42 的最大公約數(shù)，我們可將問題轉(zhuǎn)換為：求一組整數(shù)x，y 使得25x+7y=1。

這里我們應(yīng)用歐拉演段解得該問題，求出所求兩數(shù)為2 和-7，歐拉演段就不在這里演示。

即6=150×2+42×(-7)，于是x=2，y=-7 為所求。這也是輾轉(zhuǎ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é)中，它還被用來解丟番圖方程，尋找滿足中國(guó)剩余定理的數(shù)，或者求有限域中元素的逆。輾轉(zhuǎn)相除法還可以用來構(gòu)造連分?jǐn)?shù)，在施圖姆定理和一些整數(shù)分解算法中也有應(yīng)用。輾轉(zhuǎn)相除法是現(xiàn)代數(shù)論中的基本工具。