行第二步．

　　第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数．继续这个操作，直到所得的差与减数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.

知识3 秦九韶算法 　　　将f(x)改写成如下形式：f(x)＝(...((anx＋an－1)x＋an－2)x＋...＋a1)x＋a0.

　　具体算法如下：

　　(1)计算最内层括号内一次多项式的值，即v1＝anx＋an－1.

　　(2)由内向外逐层计算多项式的值，即

　　v2＝v1x＋an－2，

　　v3＝v2x＋an－3，

　　...

　　vn＝vn－1x＋a0.

类型1 用辗转相除法求最大公约数 例1　用辗转相除法求228与1 995的最大公约数．

　　【思路探究】　使用辗转相除法可根据m＝nq＋r，反复相除直到r＝0为止．

　　解：1 995＝8×228＋171，

　　228＝1×171＋57，

　　171＝3×57，

　　∴228与1 995的最大公约数为57.

　　规律方法

　　利用辗转相除法求给定的两个数的最大公约数，即利用带余除法，用数对中较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的数对，再利用带余除法，直到大数被小数除尽，则这时的较小数就是原来两个数的最大公约数．

变式训练

　　　用辗转相除法求779和209的最大公约数．

　　解：∵779＝209×3＋152，

　　209＝152×1＋57，

　　152＝57×2＋38，

　　57＝38×1＋19，

　　38＝19×2，

∴779与209的最大公约数为19.