Euclid算法

gcd(a,b)=gcd(b, a+kb) a,b,k为任意整数

􀂨gcd(a,b)=gcd(b, a mod b) a≥0,b>0

• Example:gcd(55,22)=gcd(22, 55mod22)

=gcd(22,11)=11

• 证明：假定d=gcd(a,b)，那么有d|a和d|b.对任何正整数b,a

可表示为如下形式： a=kb+r ≡r mod b, a mod b =r , 因

此，有(a mod b )= a-kb，k为某个整数。但由于d|b，b也

能整除kb, 而d|a，故有d|(a mod b), 这表明d 也是b 和(a

mod b) 的公因子。由于这是可逆的，如果d 是b 和(a mod

b) 的公因子，那么d|kb，且d|[kb+（a mod b)],这等同于

d|a。这样a和b的公因子集合等同于b 和(a mod b) 的公因

子集合。