假設有兩個數x和y，存在一個最大公約數z=(x,y)，即x和y都有公因數z，那麼x一定能被z整除，y也一定能被z整除，所以x和y的線性組合mx±ny也一定能被z整除。（m和n可取任意整數）對於輾轉相除法來說，思路就是：若x>y，設x/y=n餘c，則x能表示成x=ny+c的形式，將ny移到左邊就是x-ny=c，由於一般形式的mx±ny能被z整除，所以等號左邊的x-ny（作為mx±ny的一個特例）就能被z整除，即x除y的餘數c也能被z整除。
若不能整除，則將min{x,y}作為被除數，餘數c作為除數，繼續迴圈這個過程，直到餘數c=0為止。為什麼這樣做可以得到結果？因為在這個過程中，被除數和除數最大公約數始終沒有變。分析如下：
設商為f,假設第十一步得到了結果，迴圈過程：x/y=f1…c1y/c1=f2…c2c1/c2=f3…c3……c8/c9=f10…c10c9/c10=f11…0如此，c10即為最大公約數。那麼據第一段所述，可得：c9%c10=0，c8%c10=0，c7%c10=0……c1%c10=0，據此可說明被除數和除數最大公約數始終沒有變。於是這樣就得到了最大公約數了。
備註：兩個整數的最大公約數等於其中較小的數和兩數的差的最大公約數最小公倍數等於兩個數的乘積除以最小公約數b能被a整除<=>b/a=c…0 (c為整數);b能整除a<=>a/b=c’…0(c為整數).
假設有兩個數x和y，存在一個最大公約數z=(x,y)，即x和y都有公因數z，那麼x一定能被z整除，y也一定能被z整除，所以x和y的線性組合mx±ny也一定能被z整除。（m和n可取任意整數）對於輾轉相除法來說，思路就是：若x>y，設x/y=n餘c，則x能表示成x=ny+c的形式，將ny移到左邊就是x-ny=c，由於一般形式的mx±ny能被z整除，所以等號左邊的x-ny（作為mx±ny的一個特例）就能被z整除，即x除y的餘數c也能被z整除。
若不能整除，則將min{x,y}作為被除數，餘數c作為除數，繼續迴圈這個過程，直到餘數c=0為止。為什麼這樣做可以得到結果？因為在這個過程中，被除數和除數最大公約數始終沒有變。分析如下：
設商為f,假設第十一步得到了結果，迴圈過程：x/y=f1…c1y/c1=f2…c2c1/c2=f3…c3……c8/c9=f10…c10c9/c10=f11…0如此，c10即為最大公約數。那麼據第一段所述，可得：c9%c10=0，c8%c10=0，c7%c10=0……c1%c10=0，據此可說明被除數和除數最大公約數始終沒有變。於是這樣就得到了最大公約數了。
備註：兩個整數的最大公約數等於其中較小的數和兩數的差的最大公約數最小公倍數等於兩個數的乘積除以最小公約數b能被a整除<=>b/a=c…0 (c為整數);b能整除a<=>a/b=c’…0(c為整數).