定理的证明 shall then prove that the lemma holds for k recursive calls.Since k >0,we have b>0,and EUCLID(a,b)calls EUCLID(b,a mod b)recursively,which in turn makes k-1 recursive calls.The inductive hypothesis then implies that bF+ (thus proving part of the lemma),and a mod b>F.We have b+(a mod b)b+(a-bla/b]) ≤a, since a >b>0implies a/b]>1.Thus, a ≥b+(a mod b) Fk+1+Fk Fk+2·定理的证明