這個不難,去翻翻《近世代數(shù)》,《數(shù)論》,這種書上都有的,我在此稍微寫一下,：
首先給定兩個數(shù)a,b（a>b）,則根據(jù)除法運算,a/b=q.r.q是商,r是余數(shù).也可以表示為a=bq+r.這是小學就知道的.
下面給出一個定理：
若a=bq+r,則（a,b）=（b,r）,即a,b的最大公約數(shù)等于b,r的最大公約數(shù).
舉個例子來說：
24=10*2+4,那么(24,10)=(10,4)=2
這個定理的證明也很簡單.
設(shè)c是a和b的任意一個公約數(shù),則c能同時整除a和b,即a=cx,b=cy,（x,y是整數(shù)）
將它們代入“a=bq+r”中：
cx=cyq+r
得到r=c(x-yq),說明c也能整除r,即c也是b和r的公約數(shù).
于是a和b的公約數(shù)就是b和r的公約數(shù),那么a和b最大公約數(shù)就是b和r的最大公約數(shù),（a,b）=（b,r）.
定理得證.
歐幾里德算法就是對照這個定理來做的,每一次輾轉(zhuǎn)相除其實就是用了一次上面的定理,一步一步遞推得到最后結(jié)果.