歐幾里德算法又稱輾轉相除法，用于計算兩個整數(shù)a,b的最大公約數(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
假設d是a,b的一個公約數(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
