數學探秘 輾轉相除法

大虎學會了用短除法來求最大公因數，他發現用這個方法比用列舉法算得快多了，他正在向周圍的同學炫耀，這時小芳說話了：“大虎，你能求3139和2117的最大公因數嗎？我正在解決這個問題，感覺太難了?！毙判臐M滿的大虎前來應戰：“好，我來試試，用質數2試試，2不是它們的公因數，用3試試，不行，用5試試，還不行，7、11、13、…都不行！”滿頭大汗的大虎突然發現短除法不好使了，于是宣布道：“這兩個數就沒有公有的質因數，因此，它們的最大公因數就是1?！?/p>

“哈哈，雖然試了這么多的數都不行，但也不能斷定這兩個大數的最大公因數就是1吧？其實我也不知道它們的最大公因數是多少?！毙》颊f道。

同學們都好奇地議論起來，但沒有同學能確定最后的答案。

正當同學們抓耳撓腮的時候，阿帥老師來解圍了：“當兩個數都比較大時，還有一種更為簡單的求最大公因數法——輾轉相除法?！?/p>

“什么？輾轉相除法？難道是在地上來回打幾個滾，就能得出這兩個數的最大公因數嗎？”聽大虎這么一說，大家都大笑起來。

“像來回打滾一樣簡單！”阿帥老師笑著說，“不相信，我們現在就來試試吧。”

阿帥老師接著說：“我們就以課上討論過的題目為例來講這種方法吧，這樣更好理解?！?/p>

“兩個數的最大公因數可以用如下的符號來表示?！?/p>

“你們可以用兩個數中較大的數除以較小的數，看看余數與最大公因數之間有什么樣的關系。”

小陽說：“我發現了，前面兩個除法算式的余數正好等于被除數和除數的最大公因數，可最后一個算式不是這樣的。”

阿帥老師說：“最后一個除式，你用除數48再除以所得的余數18，看看有什么新的發現。如果沒有發現，繼續這樣操作幾次?！?/p>

大虎：“啊，真的有關系哎，這樣算幾次之后最終的余數就是兩個數的最大公因數，這是為什么呢？”

阿帥老師：“這樣算看起來神秘，其實仔細想想，道理很簡單。以12和18為例，6是12和18的公因數，那么6是不是也是18和12的差的公因數？”

讓我們想想……

小芳：“我明白了，6是12和18的公因數，從6的倍數18中減去6的倍數12，得到的數也一定是6的倍數。因為6的一個較大的倍數減去6的一個較小的倍數，所得的差一定也是6的倍數?！?/p>

阿帥老師：“道理是正確的，那么，你們再試著想想（162，48）=6這個式子。”

小陽：“6是162和48的公因數，162÷48=3……18，從6的倍數162中減去6的倍數48×3=144，得到的數18也一定是6的倍數；48÷18=2……12，然后從6的倍數48中減去6的倍數18×2=36，剩余的部分12也一定還是6的倍數；18÷12=1……6，接著從6的倍數18中減去6的倍數12×1，剩余的部分6也一定還是6的倍數。余數6正好是最大公因數6，證明完畢?！?/p>

大虎：“我們事先已經知道最大公因數是6，要是不知道，那要除到什么時候結束呢？”

阿帥老師：“那我們就接著除，看看會怎樣。從6的倍數12中去掉6的倍數6×2=12，得到的數為0。那么是不是所有的題目這樣算最后得到的數都一定為0呢？我來用前面兩個例子試一試。”

大虎：“還真的是啊，按照這樣的方法一直除下去，最后所得的余數一定為0。那么，這兩個數的最大公因數就是倒數第二個算式的余數?！?/p>

阿帥老師：“說得好，把我想說的都說完了?！?/p>

大虎：“青出于藍而勝于藍?！?/p>

阿帥老師：“前面的問題還沒有解決呢，誰來試試求3139和2117的最大公因數是多少？”

大虎：“我想試一試?！?/p>

阿帥老師：“73是不是3139和2117的最大公因數呢？大家用前面學習的方法驗證一下?！?/p>

小陽：“我來用短除法驗證。”

“43和29互質，只有公因數1?！?/p>

大虎：“我用分解質因數的方法來試一試?！?/p>

“73確實是3139和2117的最大公因數?！?/p>

同學們用不同的方法驗證了結果，阿帥老師感覺很欣慰。

延伸閱讀

南北朝時，李謐拜孔璠為師。

李謐潛心向孔璠求教，由于他功底深厚，又勤奮好學，所以進步很快。過了幾年，李謐的學問超過了他的老師，孔璠對此很是高興。有時，孔璠有了疑難問題還要向李謐請教，而李謐覺得很不好意思，孔璠很誠懇地對他說：“你不要覺得不好意思。只要在某一方面比我有學問的人，都可以做我的老師。學生勝過先生，后人勝過前人，一代更比一代強，這也是我做老師的愿望?！?/p>