Question

中国古代数学著作《九章算法》中的“更相减损术”可用来求两个正整数的最大公约数．现应用此法求168与93的最大公约数：记（168，93）为初始状态，则第一步可得（75，93），第二步得到（75，18），…．以上解法中，不会出现的状态是（　　）

• A、（57，18）
• B、（3，18）
• C、（6，9）
• D、（3，3）

Answer 1

考点：辗转相除法

专题：算法和程序框图

分析：本题考查的知识点是最大公因数和更相减损术，我们根据“以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数．继续这个操作，直到所得的减数和差相等为止．”的原则，易求出168与93的最大公约数．然后找出选项．

解答： 解：168-93=75，
93-75=18，
75-18=57，
57-18=39，
39-18=21，
21-18=3，
18-3=15．
15-3=12．
12-3=9
9-3=6．
6-3=3
因此168与93的最大公约数是3．
记（168，93）为初始状态，则第一步可得（75，93），第二步得到（75，18），…．以上解法中，不会出现的状态是（6，9）．
故选：C．

点评：更相减损术的方法和步骤是：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数．继续这个操作，直到所得的减数和差相等为止．