(3)令x=a,x=b,i=0; (4)i=t+1,x+1=x-1%0.x (5)如果x>0,返回到第(4)步 (6)(a,b)=x。 上述算法被称为广义欧几里得除法。 由性质1(i)和(i)我们知道,在步骤(4)中可 以使用绝对值最小余数,这种方法在a和b都比较大 时,算法的复杂性会降低。我们可以看看例2(2)使 用绝对值最小余数的另一种解法:此解法的运算次数 比算法1.2.1少了3次 在辗转相除法具体求两个整数的最大公因数(a,b)=F 的过程中,从倒数第二个式子开始把所有的等式移项 后可得 rd 73=F1-2a 厂2=b-ra1, 7=a b 逐次消除r,F3,…r,r,则可以找到整数s,使得 sa+tb=(a, b=r 例3运用上述方法求整数s,t,使得s+tb=(a,b)（3）令 x0 = a, x1 = b ， i = 0 ； （4） i = i +1 ， i i i x x %x +1 = −1 ； （5）如果 xi+1  0 ，返回到第（4）步； （6） i (a,b) = x 。 上述算法被称为广义欧几里得除法。 由性质 1（ⅰ）和（ⅱ）我们知道，在步骤（4）中可 以使用绝对值最小余数，这种方法在 a和b 都比较大 时，算法的复杂性会降低。我们可以看看例 2（2）使 用绝对值最小余数的另一种解法：此解法的运算次数 比算法 1.2.1 少了 3 次。 在辗转相除法具体求两个整数的最大公因数 N (a,b) = r 的过程中，从倒数第二个式子开始把所有的等式移项 后可得 N = N−2 − N−1aN−1 r r r N−1 = N−3 − N−2 aN−2 r r r …… 3 1 2 a2 r = r − r ， 2 1a1 r = b − r ， 1 a ba0 r = − 逐次消除 1 2 2 1 r ,r , r ,r N− N−  ，则可以找到整数 s,t 使得 N sa + tb = (a,b) = r 例 3 运用上述方法求整数 s,t ，使得 sa + tb = (a,b)