Question

（1）用辗转相除法求123和48的最大公约数.

（2）用更相减损术求80和36的最大公约数.

Answer 1

解：（1）辗转相除法求最大公约数的过程如下：

123＝2×48＋27，

48＝1×27＋21，

27＝1×21＋6，

21＝3×6＋3，

6＝2×3+0，

最后6能被3整除，得123和48的最大公约数为3.

（2）我们将80作为大数，36作为小数，因为80和36都是偶数，要除公因数2.

80÷2=40，36÷2=18.

40和18都是偶数，要除公因数2.

40÷2=20，18÷2=9.

下面来求20与9的最大公约数，

20－9=11，

11－9=2，

9－2=7，

7－2=5，

5－2=3，

3－2=1，

2－1=1，

可得80和36的最大公约数为2²×1=4.

点评：对比两种方法控制好算法的结束，辗转相除法是到达余数为0，更相减损术是到达减数和差相等.