輾轉(zhuǎn)相除法
定理： gcd(a, b) = gcd(b, a mod b)
證明：
a可以表示成a = kb + r, 則r = a mod b
假設(shè)d是a, b的一個(gè)公約數(shù), 則有d|a, d|b, 而r = a - kb, 因此d|r.
因此,d是(b, a mod b)的公約數(shù).
加上d是(b,a mod b)的公約數(shù),則d|b, d|r, 但是a = kb + r,因此d也是(a, b)的公約數(shù).
因此,(a, b) 和(a, a mod b)的公約數(shù)是一樣的,其最大公約數(shù)也必然相等,得證.