吉祥農場

　　「給定一個長與寬都是正整數的長方形，起先用刀子割去最大可能的正方形；剩下部分再割去最大可能的正方形；……；如此進行下去，直到最後剩下的長方形是正方形就停止。最後的正方形的邊長是什麼呢？」

　　答：長和寬的最大公因數。

　　如列圖就是一個□_{１４╳１０}的長方形先割去□_１０、在割去２個□_４、最後剩下２個□_２。最後的正方形數□_２邊長２就是１０和１４的最大公因數。

　這就是輾轉相除法的作法，輾轉相除法又名歐幾里得算則（Euclidean algorithm），在求兩個正整數之最大公因數。是目前已知最古老的算則，首次出現於歐幾里得的《幾何原本》，卷七命題一是這樣描述這個算法的：

　「設有不相等的二數，從大數中連續減去小數直到餘數小於小數，再從小數中連續減去餘數直到小於餘數，這樣一直作下去，若餘數總是量不盡其前個數，直到最後的餘數為一個單位，則該二數互質。」

　　當某數量盡它前面的數時，歐幾里得就在卷七命題二中利用線段拼量證明了這數就是初始兩數的最大公因數。在這邊把線段變成了長和寬是同樣思了。

　　我們如果仔細觀察，就會發現，每次割去的正方形邊長，都是２的倍數，而剩下來的邊長也是２的倍數，因此長和寬的最大公因數不會消失，直到最後最大公因數直接浮現出來，是不是很巧妙呢？

　　那麼在用另外一個例子說明，這次用□_{３４╳１０}

　　可以看出□_１０的有３個；□_４有２個，□_２有２：所以最大公因數是２。

　　如果我們直接用筆算，還可以寫成下式：

　　先劃三條直線，將３４和１０寫在二條直線中，接下來割３個１０的正方形，將３寫在３４的外側，而３╳１０＝３０寫在３４的下方，並劃出一橫將二數相減得到４。意思就是割去３０後，長剩下４。

　　同法，在１０這邊割去２個４的正方形，將２寫在１０的外側，而２╳４＝８寫在１０的下方，並劃出一橫將二數相減得到２。

　　最後得到０，在０之前的那個２就是最大公因數。可以看出□_１０的有３個；□_４有２個，□_２有２。

　　有沒有很巧妙呢？自己可以試看看喔！

問題與討論：

問題一：小張要把一張長80公分，寬50公分的紙，剪成n個正方形(每個面積大小不一定)，求n的最小值。

問題二：裴蜀定理：對於任意給定的正整數a; b 則必定存在整數p; q 使得(a,b)= ap+ bq,其中的p; q 稱為裴蜀系數：例如(4,10)=2，則存在整數3;-1，使得

2=3╳4+10╳(-1) 。那你能找到(3,7)的裴蜀系數嗎？

　　　歡迎把問題與討論的答案寄到電子信箱：guevara4900@gmail.com或是寫信到:雲林縣斗六巿江厝里部子23號，數學玩玩收．答的好的朋友將致贈薄禮！

文／施朝祥2018.12.8　于廖廍仔莊竹圍仔吉祥自然農場