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

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

連結：輾轉相除法(III)

一、五猴分桃問題：

五隻猴子分一堆桃子，怎麼分也不能均分成五份，大家約定先去睡覺，明天再說。夜裡，猴甲偷偷起來，吃掉一個，這時發現其餘正好可以分成五份，結果猴甲把自己那份藏起來，又躺去睡覺了；接著猴乙也偷偷起來，吃掉一個，發現其餘也正好可以分成五份，結果猴乙也把自己那份藏起來；猴丙，猴丁，都如法炮製。而猴戊吃掉一個後，也發現餘桃數為 $$5$$ 的倍數。問總桃數最少有幾個？

參考解法：

假設總桃數為 $$x$$，而 $$y$$ 為某個正整數。

因為 $$\displaystyle\frac{1}{5}\left[ {\frac{4}{5}\left[ {\frac{4}{5}\left[ {\frac{4}{5}\left[ {\frac{4}{5}\left( {x – 1} \right) – 1} \right] – 1} \right] – 1} \right] – 1} \right] = y$$

整理方程式得：$$256x-3125y=2101$$ (此即為不定方程式)，

利用歐幾里得的想法，我們先考慮 $$256x+3125y=1$$

$$\begin{array}{rl} 3125 &=12 \times 256+53\\256&=4\times 53+44\\53&=1\times 44+9\\44&=4\times 9+8\\9&=1\times 8+1\end{array}$$

反運算得：

$$\begin{array}{ll}1 &= 9-8\\&= 9-(44-4\times 9)\\&=5\times 9-44\\&=5\times(53-44)-44\\&=5\times 53-6\times 44\\&=5\times 53-6\times (256-4\times 53)\\&=29\times 53-6\times 256\\&=29\times (3125-12\times 256)-6\times 256\\&=256\times(-354)+3125\times 29\end{array}$$

所以，方程式 $$256x+3125y=1$$ 便有一組解：$$x=-354,~ y=29$$

當方程式 $$256x+3125y=1$$ 同乘 $$2101$$時，便得：

$$256\times (-743754)-3125\times (-60929)=2101$$

所以，方程式 $$256x-3125y=2101$$ 有一組解：$$x=-743754, y=-60929$$

則通解為：$$(x,y)=(3125t-743754,256t-60929)$$，$$t\in \mathbb{R}$$

根據題意，因為 $$x$$ 為正整數，所以，$$x > 0,\therefore t > \frac{{743754}}{{3125}} > 238$$，

所以，$$t$$ 取 $$239$$ 為最小值滿足題意。

所以，$$x = 3125\times 239-743754 = 3121$$ 為總桃數。

類似問題有：【物不知數】《孫子算經》：「有一批物品，不知有多少件。每三件一數，剩二件；每五件一數，剩三件；每七件一數，剩二件，問此批物品共有多少件？」楊輝著《續古摘奇算法》【物不知數】：「二數餘一，五數餘二，七數餘三，九數餘四，問原總數為何？」

二、輾轉相除法與斐波那契數列

「每一對兔子過了出生第一個月之後，每個月生一對小兔子。現把一對初生小兔子放在屋內，問一年後屋內有多少對兔子？」我們發現一個規律：

由此可得，每個月的兔子總數是

$$1,~1,~2,~3,~5,~8,~13,~21,~34,~55,~89,~144,~233,~377…$$，

由此可知一年後有 $$377$$ 對兔子。若把上述數列繼續寫下去，得到的數列便稱為斐波那契數列。

數列中每個數便是前兩個數之和，而數列的最初兩個數都是 $$1$$。

如果設 $$F_1=1,~F_2=1,~F_3=2,~F_4=3,~F_5=5,~F_6=8,~F_7=13…$$

則成立這個關係式：當 ，$$F_{n+2}=F_{n+1}+F_n$$，而 $$F_1=F_2=1$$。

最後得到下面神奇的式子：

$$\displaystyle {F_n} = \frac{1}{{\sqrt 5 }}\left[ {{{(\frac{{1 + \sqrt 5 }}{2})}^n} – {{(\frac{{1 – \sqrt 5 }}{2})}^n}} \right]$$，可用數學歸納法來證明。

最後談談輾轉相除法與斐波那契數列的關係，若我們定義 $$E(m,n)$$ 為兩正整數 $$m,n$$ 利用輾轉相除法時所需要的步驟，那麼

$$E(F_3,F_2)=E(2,1)=1 \\E(F_4,F_3)=E(3,2)=2 \\E(F_5,F_4)=E(5,3)=3 $$

利用輾轉相除法我們不難證明出 $$E(F_{n+1},F_{n+1})=n$$，那麼這有些幫助呢?想想輾轉相除法(II)歐氏遊戲的必勝條件吧！

參考資料：

1. 蔡聰明，《數學的發現趣談》，台北：三民書局，2000。