辗转相除法
zhǎn/niǎn zhuǎn/zhuàn xiāng/xiàng chú fǎ
求两个正整数的最大公约数的算法。设两数为a、b(b<a),求它们最大公约数(a、b)的步骤如下:用b除a,得a=bq_1+r_1(0≤r_1<b)。若r_1=0,则(a,b)=b;若r_1≠0,则再用r_1除b,得b=r_1q_2+r_2(0≤r_2<r_1)。若r_2=0,则(a,b)=r_1,若r_2≠0,则继续用r_2除r_1,……如此下去,直到能整除为止。其最后一个非零余数即为(a,b)。类似地,求两个多项式的