“辗转相除法”和“更相减损术”溯源

龙源期刊网 http://www.qikan.com.cn

“辗转相除法”和“更相减损术”溯源

作者：严家丽

来源：《中学数学杂志(高中版)》2012年第06期

人民教育出版社出版的普通高中课程标准实验教科书《数学③》（必修）第一章“算法初步”中的1.3节“算法案例”中引入了“辗转相除法”与“更相减损术”的算法案例，教科书主要通过举例集中呈现“辗转相除法”与“更相减损术”的算法过程和递归的算法思想，但没有细致揭露其中蕴含的算理，回答了是什么的问题，没有回答为什么的问题.作为教师，需要超越教科书的视野限制，懂得知识的来龙去脉，特别是教科书中涉及到的古代数学史部分，需要探究其发生发展的过程，这样才能在教学时有更深刻的体会，才会情不自禁地感染学生.据此，本文觉得有必要对“辗转相除法”与“更相减损术”做一下梳理，并以此为例，探究教师解读教科书的方法. 1 什么是“辗转相除法”与“更相减损术”

根据数学史料记载，“辗转相除法”是公元前三百多年前的古希腊数学家欧几里得

（Euclid）在《几何原本》（第Ⅶ卷，命题ⅰ和命题ⅱ）中首先提出的求最大公约数的方法，所以“辗转相除法”又称为“欧几里得算法”.目前见到书中介绍的“辗转相除法”主要有以下几种： 第一种来自兰纪正、朱恩宽翻译的陕西科学技术出版社出版的《欧几里得几何原本》：“设有不相等的二数，若依次从大数中不断地减去小数，若余数总是量不尽它前面一个数，直到最后的余数为一个单位，则该二数互素.若两数不互素，则依次从大数中不断减去较小者，将有某个余数能量尽它前面一个，而且这最后的余数不是一个单位”[1].

第二种来自李善兰翻译的《几何原本》中的阐述：“两不（相）等数，辗转相减，余一而止，则为两无等数之数.两数非无等数，求其最大等数.法曰：……辗转以小减大，必有减余数可度两数，而减余非为一.若余一，则为无等之数，而与所设之题相反矣，故最后减余数必为等数也”[2].

第三种来自张奠宙、孔凡哲、黄建弘、黄荣良、唐彩斌著的《小学数学研究》：“若a与b是两数，且a>b，从a减去足够多次的b，一直到余数r小于b；然后再从b中减去足够多次的r，直到余数小于r，如此往下进行.若a与b互质，最后余数是1，那么1就是它们的最大公因数；若a与b不互质，就会在某一阶段出现最后一致除尽前一个数的情况，于是这最后的数便是a与b的最大公因数”[3].

第四种来自普通高中课程标准实验教科书《数学③》（必修）中的阐述：“例如用辗转相除法求8251与6105的最大公约数，我们可以考虑用两数中较大的数除以较小的数求得商和余数：8251=6105×1+2146.由此可得，6105与2146的公约数也是8251与6105的公约数，反过来，8251与6105的公约数也是6105与2146的公约数，所以它们的最大公约数相等.对6105与2146重复上述步骤：6105=2146×2+1813，继续重复上述步骤：2146=1813×1+333，