可能是世界上最古老的算法 EUCLID(a,b) 1 ifb==0 2 return a 3 else return EUCLID(b.a mod b) Theorem 31.9(GCD recursion theorem) For any nonnegative integer a and any positive integer b, gcd(a,b)=gcd(b,a mod b). 证明的关键：a mod b可以表示为和的线性组合：a-qb; 所以gcd(a,b)可以整除(a mod b),所以可以整除gcd(b,a odb)；类似地可以证明后者也可以整除前者，两者均为 正，所以相等。可能是世界上最古老的算法 证明的关键：a mod b 可以表示为a和b的线性组合：a-qb； 所以gcd(a,b)可以整除(a mod b), 所以可以整除gcd(b, a mod b)；类似地可以证明后者也可以整除前者，两者均为 正，所以相等