(ii)对任意整数s,t,必有(a,b)(sa+tb); 例1设p是一个素数,a为整数。如果pa,则p与a 互素。 从上面例题可以看出若p是一个素数,则对于任意整 数a,(p,a)=p或者(p,a)=1 由性质1(ⅱ)可由下述辗转相除法具体求出两个整 数的最大公因数(a,b)=F a=be 0≤r<b b=ra.+r, 0≤r<r; F=F2a2+n3, 0≤r<F; r-a- +IN 0 NN-=ln 因为r,r…,r是一个单调有界非负序列,所以必然存 在有限步达到上述最后一个等式。 例2(1)设a=-793,b=2769,计算(a,b); (2)设a=1435,b=3371,计算(a,b)。 上面计算过程可以总结为如下算法: 求任意两个整数a和b最大公因数算法: 算法1.2.1(1)如果a<0,则a=-a,如果b<0,则 6=-b (2)如果a+b=0,则输出“整数a和b无 最大公因数”,结束程序;（ⅲ）对任意整数 s,t ，必有 (a,b)| (sa + tb) ； 例 1 设 p 是一个素数， a 为整数。如果 p | a ，则 p 与 a 互素。 从上面例题可以看出若 p 是一个素数，则对于任意整 数 a ， ( p,a) = p 或者 ( p,a) =1 由性质 1（ⅱ）可由下述辗转相除法具体求出两个整 数的最大公因数 N (a,b) = r ： 0 1 a = ba + r ， 0  r1  b ； 1 1 2 b = ra + r ， 0 2 1  r  r ； 1 2 2 3 r = r a + r ， 0 3 2  r  r ； N N N N r = r a + r −2 −1 −1 ， 0  N  N−1 r r ； N N aN r = r −1 ， 因为 N r,r , ,r 1 2  是一个单调有界非负序列，所以必然存 在有限步达到上述最后一个等式。 例 2 （1）设 a = −793,b = 2769 ，计算 (a,b) ； （2）设 a =1435,b = 3371 ，计算 (a,b)。 上面计算过程可以总结为如下算法： 求任意两个整数 a 和 b 最大公因数算法： 算法 1.2.1 （1）如果 a  0 ，则 a = −a ，如果 b  0 ，则 b = −b ； （2）如果 a + b = 0 ，则输出“整数 a 和 b 无 最大公因数”，结束程序；