趣味数学故事72……辗转相除法

        在我国古代，人们就开始利用辗转相除法来求较大的两个数的最大公因数了。

        用辗转相除法求两个数的最大公因数的步骤如下：

        先用大的数除以小的数，得第一个余数；

        再用小的数除以第一个余数，得第二个余数；

        又用第一个余数除以第二个余数，得第三个余数……

        这样依次除下去，直到余数是0为止。那么，最后一个除数就是所求的最大公因数（如果最后的除数是1, 那么原来的两个数是互质数）。

        例如，求195和900的最大公因数，

        第一次：用900除以195, 商4余120；

        第二次：用195除以120, 商1余75；

        第三次：用120除以75, 商1余45；

        第四次：用75除以45, 商1余30；

        第五次：用45除以30, 商1余15；

        第六次：用30除以15, 商2余0。

        因此，195和900的最大公因数是15。

        辗转相除法是求两个数的最大公因数的方法。如果求几个数的最大公因数，可以先求两个数的最大公因数，再求这个最大公因数与第三个数的最大公因数。这样依次下去，直到最后一个数为止。最后所得的一个最大公因数，就是所求的几个数的最大公因数。