原理：
設兩數為a、b(a>b)，用gcd(a,b)表示a，b的最大公約數，r=a (mod b) 為a除以b的余數，k為a除以b的商，即a÷b=k.......r。輾轉相除法即是要證明gcd(a,b)=gcd(b,r)。
第壹步：令c=gcd(a,b)，則設a=mc，b=nc
第二步：根據前提可知r =a-kb=mc-knc=(m-kn)c
第三步：根據第二步結果可知c也是r的因數
第四步：可以斷定m-kn與n互質(假設m-kn=xd，n=yd (d>1)，則m=kn+xd=kyd+xd=(ky+x)d，則a=mc=(ky+x)cd，b=nc=ycd，則a與b的壹個公約數cd>c，故c非a與b的最大公約數，與前面結論矛盾)，因此c也是b與r的最大公約數。
從而可知gcd(b,r)=c，繼而gcd(a,b)=gcd(b,r)。
證畢。
以上步驟的操作是建立在剛開始時r≠0的基礎之上的。即m與n亦互質。
解釋：
輾轉相除法， 又名歐幾裏德算法（Euclidean algorithm）乃求兩個正整數之最大公因子的算法。它是已知最古老的算法， 其可追溯至公元前300年前。
來源：
設兩數為a、b(a>b)，求a和b最大公約數(a，b)的步驟如下：用a除以b，得a÷b=q......r1(0≤r1)。若r1=0，則(a，b)=b；若r1≠0，則再用b除以r1，得b÷r1=q......r2?(0≤r2）.若r2=0，則(a，b)=r1，若r2≠0，則繼續用r1除以r2，……如此下去，直到能整除為止。其最後壹個余數為0的除數即為(a, b)的最大公約數。
例如：a=25,b=15，a/b=1......10,b/10=1......5,10/5=2.......0,最後壹個余數為0d的除數就是5, 5就是所求最大公約數。
舉例說明：
不定方程為326x+78y=4，求出壹組整數解x,y
求（326,78）的算式為：
326=4*78+14
14=326-4*78
78=5*14+8
8=78-5*14
14=1*8+6
6=14-1*8
8=1*6+2
2=8-1*6
6=3*2
所以
2=8-6=8-（14-8）
=2*8-14=2*（78-5*14）-14
=2*78-11*14=2*78-11*（326-4*78）
=46*78-11*326
即2=(-11)*326+46*78
所以4=(-22)*326+92*78
所以x = - 22, y = 92是不定方程326x+78y=4的壹組解。