Theorem 2.4 Let a and b be nonzero integers.Then there exist integers r and s such that ged(a,b)ar +bs. Furthermore.the areatest common divisor of a and b is unique. PROOF.Let S=fam+bn m,n EZ and am on>0}. ←一α，b所有的正的线性组合 Clearly,the set S is nonempty;hence,by the Well-Ordering Principle S must have a smallest member,say d ar+bs.We claim that d ged(a,b). ←一构造出“最大公因子 Write a =dg+r where 0<r<d.If r>0,then r a-dg a-(ar+bs)q “最大公因子”是公因子 a-arg bsq 现在你知道如何“算”出 =a(1-rq）+b(-sq), ab的最大公因子了吗？ which is in S.But this would contradict the fact that d is the smallest member of S.Hence,r=0 and d divides a.A similar argument shows that d divides b.Therefore,d is a common divisor of a and b. Suppose that d'is another common divisor of a and b,and we want to show that d'd.If we let a =d'h and b=d'k,then 而且一定是 d=ar +bs d'hr +d'ks d'(hr +ks). 最大公约数 So d'must divide d.Hence,d must be the unique greatest common divisor of a and b. ▣而且一定是 最大公约数 a,b所有的正的线性组合 构造出“最大公因子” 现在你知道如何“算”出 ab的最大公因子了吗？ “最大公因子”是公因子