輾轉相除法(II) (Euclidean algorithm)

輾轉相除法(II) (Euclidean algorithm)
國立蘭陽女中數學科陳敏晧老師

連結：輾轉相除法(I)

一、畢氏音律與輾轉相減法

西元前五百多年，畢達哥拉斯(Pythagoras of Samos, c. 570 BC – c. 495 BC)(如右圖)為了探求音律，利用單弦琴(monochord)作實驗，發現兩個音的弦長為簡單整數比時，是和諧悅耳的。例如：$$2:1$$，$$3:2$$，$$4:3$$，$$5:4$$ 分別是八度、五度、四度及三度音程。這些弦長的比是如何求得的呢？若是分成 $$3:2$$，則會產生悅耳的和弦音樂，因此，不同的弦長比例會導致不同的音高，若是比例不正確，則會形成不和諧的和弦聲。

原來畢達哥拉斯是利用逐步相減法(the successive subtraction)求得的：考慮 $$a$$、$$b$$ 兩弦，不妨設 $$a>b$$，從 $$a$$ 減去較小的 $$b$$，得 $$a-b$$；若 $$a-b$$ 仍大於 $$b$$，再減去 $$b$$ 得 $$a-2b$$；…，直到 $$a-tb\le b$$，其中 $$t\in\mathbb{N}$$。繼續從較大的 $$b$$ 減去較小的 $$a-tb$$，…，直到 $$b-l(a-tb)\le a-tb$$，其中$$l\in\mathbb{N}$$。按此要領反覆做下去，經過有限步的輾轉相減後，必可得到 $$0$$，此時運算停止。在 $$0$$ 之前最後一個不為 $$0$$ 的數 $$d$$，即最大公因數 $$d$$。

畢達哥拉斯相信，任意給定兩正整數 $$a$$、$$b$$，必可利用有限次的逐步相減運算，找到最後一個不為 $$0$$ 的正整數 $$d$$，所以，存在正整數 $$p$$、$$q$$，使得 $$a=pd~, b=qd$$，而 $$d$$ 為滿足此式的最大弦長，從而得到 $$a:b =p:q$$ 為整數比，我們稱這種演算法稱為輾轉相減法。

另外，當時畢氏還無法利用頻率來實驗，僅能根據弦長來驗證音與音之間的比，他利用「五度音循環法」，由 $$1$$ 出發，連續升高五度(即連續乘以 $$\frac{3}{2}$$ 五次)，即 $$1,~\frac{3}{2},~\frac{9}{4}(>2),~\frac{27}{8}(>2),~\frac{81}{16}(>2),~ \frac{243}{32}(>2)$$ 再把超過八度的音降低八度(除以 $$2$$)，或低於八度音的升高八度(乘以 $$2$$)，由小至大得 $$1,~\frac{9}{8},~\frac{81}{64},~\frac{3}{2},~\frac{27}{16},~\frac{243}{128},~2$$，缺乏第四音由 $$1\times \frac{2}{3}=\frac{2}{3}$$，再 $$\frac{2}{3}\times 2 =\frac{4}{3}$$，就可以得到如下表的畢氏音階。

二、歐氏遊戲與輾轉相除法

從畢氏求音律的輾轉相減法，若每次減盡，則稱為歐幾里得輾轉相除法，歐幾里得是希臘的數學家，曾任教於亞歷山大學院，輾轉相除法告訴我們：給定兩個正整數 $$a$$、$$b$$，在有限且規律的步驟裏，可以算出他們的最大公因數。一個有趣的遊戲很自然的發生了，這個遊戲我們稱為歐氏遊戲(Euclidean game)，這是兩人玩的數學遊戲，比賽規則如下：

1. 雙方各自寫一個自然數，猜拳以決定誰先開始。
2. 先者從較大的數減去較小數的任何倍數，但不能變為負數，後者亦然。
3. 兩人輪流比賽，先出現 $$0$$ 者，得勝。

所以，假使甲、乙兩人比賽，分別寫出 $$58$$ 與 $$45$$ 兩個數，假設由甲先開始，整個對局的過程可能是：

1. 
   經過5步後，甲獲勝。

也可能是：

2. 
   經過4步後，乙獲勝。

由上述情形，兩人對局時，不論先者或後者都有機會獲勝。因此，最值得關心的問題是：若 $$\{a,b\}(a>b)$$ 狀態後為 $$\{a’,b’\}(a'<b)$$，是否有必勝的絕招？先手必勝嗎？且看下面例子的說明：

1. 
   甲獲勝。
2. 
   乙獲勝。

所以，不論誰先玩，似乎並沒有必勝的絕招，不過是否能在適當的情形下，掌握致勝的先機呢？結論是可以辦到的，就請讀者思考了。

連結：輾轉相除法(III) 

參考資料：

1. 蔡聰明，《數學的發現趣談》，台北：三民書局，2000。
2. 洪萬生、英家銘、蘇意雯、蘇惠玉、楊瓊茹、劉柏宏，《當數學遇見文化》，台北：三民書局，2009。