【www.rjdtv.com--数学教学论文】

　　如何求两个正整数的最大公约数？这是高中数学必修三算法一章中的内容。用算法求解此问题时，教材中介绍了一种古老而有效的算法——辗转相除法。对于辗转相除法以及同节中的更相减损术的算法易理解，但其中的算理，不少学生甚至老师都有一些疑惑，为了解决这个疑问，笔者进行了思考。

　　一、被除数与除数的公约数集与除数与余数的公约数集相等吗

　　“用辗转相除法求 8151 与 6105 的最大公约数，我们可以考虑用两数中较大的数除以较小的数，求得商和余数：
　　8251=6105×1+2146
    由此可得，6105 与 2146 的公约数也是 8251 与 6105 的公约数，反过来 8251 与 6105 的公约数也是 6105 与 2146 的公约数，所以它们的最大的公约数相等。”
　　从以上例子中不难看出，运用了“被除数与除数的公约数集与除数与余数的公约数集相等”这一结论。下面对这一结论予以证明。
　　设 a=b×q+r，其中 a 为被除数，b 为除数，q 为商，r 为余数．
    ①设 a、b 的公约数集为 A，则，　　a=mq1,b=mq2
　　mq1= mq2q+r
　　r=m(q1-q2q)
　　故m是r的约数，所以a、b的公约数一定是b、r的公约数。
　　②设 n 为 b、r 的公约数集 B，n ∈ B，n 为 b、r 的公约数，则 b=nq1， r=nq2，
    a= nq1q+nq2
　　a=n(q1q+ q2)
　　故n是a的约数，所以b、r的公约数一定是a、b的公约数。
　　由①②知 A=B，所以被除数与除数的公约数集与除数与余数的公约数集相等。

　　二、辗转相除法与更相减损术两种方法之间有联系吗
    “用更相减损术求 98 与 63 最大公约数。
　　解：由于 63 不是偶数，把 98 和 63 以大数减小数，并辗转相减，如图示：
　　 　　所以，98 和 63 的最大公约数等于 7。”
　　将上图变化为下图：
　　 　　对比较辗转相除法，不难发现，更相减损术与辗转相除法算理一致，只不过更相减损术求解过程中的各式的商总是“1”这个定值。

　　参考文献：
　　[1] 普通高中课程标准实验教科书 · 数学 3( 必修 )．北京：人民教育出版社，2007．

本文来源：http://www.rjdtv.com/jiaoyulunwen/1222.html