数学探秘 辗转相除法

大虎学会了用短除法来求最大公因数，他发现用这个方法比用列举法算得快多了，他正在向周围的同学炫耀，这时小芳说话了：“大虎，你能求3139和2117的最大公因数吗？我正在解决这个问题，感觉太难了。”信心满满的大虎前来应战：“好，我来试试，用质数2试试，2不是它们的公因数，用3试试，不行，用5试试，还不行，7、11、13、…都不行！”满头大汗的大虎突然发现短除法不好使了，于是宣布道：“这两个数就没有公有的质因数，因此，它们的最大公因数就是1。”

“哈哈，虽然试了这么多的数都不行，但也不能断定这两个大数的最大公因数就是1吧？其实我也不知道它们的最大公因数是多少。”小芳说道。

同学们都好奇地议论起来，但没有同学能确定最后的答案。

正当同学们抓耳挠腮的时候，阿帅老师来解围了：“当两个数都比较大时，还有一种更为简单的求最大公因数法——辗转相除法。”

“什么？辗转相除法？难道是在地上来回打几个滚，就能得出这两个数的最大公因数吗？”听大虎这么一说，大家都大笑起来。

“像来回打滚一样简单！”阿帅老师笑着说，“不相信，我们现在就来试试吧。”

阿帅老师接着说：“我们就以课上讨论过的题目为例来讲这种方法吧，这样更好理解。”

“两个数的最大公因数可以用如下的符号来表示。”

“你们可以用两个数中较大的数除以较小的数，看看余数与最大公因数之间有什么样的关系。”

小阳说：“我发现了，前面两个除法算式的余数正好等于被除数和除数的最大公因数，可最后一个算式不是这样的。”

阿帅老师说：“最后一个除式，你用除数48再除以所得的余数18，看看有什么新的发现。如果没有发现，继续这样操作几次。”

大虎：“啊，真的有关系哎，这样算几次之后最终的余数就是两个数的最大公因数，这是为什么呢？”

阿帅老师：“这样算看起来神秘，其实仔细想想，道理很简单。以12和18为例，6是12和18的公因数，那么6是不是也是18和12的差的公因数？”

让我们想想……

小芳：“我明白了，6是12和18的公因数，从6的倍数18中减去6的倍数12，得到的数也一定是6的倍数。因为6的一个较大的倍数减去6的一个较小的倍数，所得的差一定也是6的倍数。”

阿帅老师：“道理是正确的，那么，你们再试着想想（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，证明完毕。”

大虎：“我们事先已经知道最大公因数是6，要是不知道，那要除到什么时候结束呢？”

阿帅老师：“那我们就接着除，看看会怎样。从6的倍数12中去掉6的倍数6×2=12，得到的数为0。那么是不是所有的题目这样算最后得到的数都一定为0呢？我来用前面两个例子试一试。”

大虎：“还真的是啊，按照这样的方法一直除下去，最后所得的余数一定为0。那么，这两个数的最大公因数就是倒数第二个算式的余数。”

阿帅老师：“说得好，把我想说的都说完了。”

大虎：“青出于蓝而胜于蓝。”

阿帅老师：“前面的问题还没有解决呢，谁来试试求3139和2117的最大公因数是多少？”

大虎：“我想试一试。”

阿帅老师：“73是不是3139和2117的最大公因数呢？大家用前面学习的方法验证一下。”

小阳：“我来用短除法验证。”

“43和29互质，只有公因数1。”

大虎：“我用分解质因数的方法来试一试。”

“73确实是3139和2117的最大公因数。”

同学们用不同的方法验证了结果，阿帅老师感觉很欣慰。

延伸阅读

南北朝时，李谧拜孔璠为师。

李谧潜心向孔璠求教，由于他功底深厚，又勤奋好学，所以进步很快。过了几年，李谧的学问超过了他的老师，孔璠对此很是高兴。有时，孔璠有了疑难问题还要向李谧请教，而李谧觉得很不好意思，孔璠很诚恳地对他说：“你不要觉得不好意思。只要在某一方面比我有学问的人，都可以做我的老师。学生胜过先生，后人胜过前人，一代更比一代强，这也是我做老师的愿望。”