歐幾里德算法又稱(chēng)輾轉(zhuǎn)相除法，用于計(jì)算兩個(gè)整數(shù)a,b的最大公約數(shù)。

基本算法：設(shè)a=qb+r，其中a，b，q，r都是整數(shù)，則gcd(a,b)=gcd(b,r)，即gcd(a,b)=gcd(b,a%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ù)

　　假設(shè)d 是(b,a mod b)的公約數(shù)，則

　　d | b , d |r ，但是a = kb +r