五猴分桃

輾轉相除法(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}$$