定義
求兩個正整數的最大公約數的算法。設兩數為a、b(b＜a)，求它們最大公約數(a、b)的步驟如下：用b除a，得a＝bq_１＋r_１（０≤r_１＜b）。若r_１=０，則(a，b)＝b；若r_１≠0，則再用r_１除b，得b＝r_１q_２＋r_２（０≤r_２＜r_１）。若r_２＝０，則(a，b)＝r_１，若r_２≠0，則繼續用r_２除r_１，……如此下去，直到能整除為止。其最後一個非零餘數即為(a，b)。類似地，求兩個多項式的最高公因式也可用此法。
原理
設兩數為a、b(b
第一步：令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)dc，b=nc=ycd，故a與b最大公約數成為cd，而非c，與前面結論矛盾】
從而可知gcd(b,r)=c，繼而gcd(a,b)=gcd(b,r)。
證畢。
應用
求不定方程的一組整數解方法
[注：以下出現的q，r括号中的是下标，gcd(a,b)為a,b的最大公約數]
輾轉相除法可以求出特定條件的不定方程的一組整數解。
設不定方程為ax+by=c，其中a,b,c為整數，且gcd(a,b)|c
a,b輾轉相除的算式為
b=qa+r
a=qr+r
r=qr+r
...
r=qr+r
r=qr
其中r=gcd(a,b)，不妨令b=r，a=r，r=0
第i個算式為
r=q×r+r
所以r=r-qr(i)(1)
用公式(1)可以得到r=gcd(a,b)關于a,b的線性組合sa+tb=gcd(a,b)
所以不定方程a×x+b×y=c的一組特解為x=s×c/gcd(a,b)y=t×c/gcd(a,b)
舉例說明
例如不定方程為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的一組解。
相關原理
兩個整數的最大公約數是能夠同時整除它們的最大的正整數。
輾轉相除法基于如下原理：兩個整數的最大公約數等于其中較小的數和兩數的相除餘數的最大公約數。
例如，252和105的最大公約數是21(252=21×12；105=21×5);
因為252÷105=242，所以(105,42)是21。在這個過程中，較大的數縮小了，所以繼續進行同樣的計算可以不斷縮小這兩個數直至餘數變為零。這時的除數就是所求的兩個數的最大公約數。由輾轉相除法也可以推出，兩數的最大公約數可以用兩數的整數倍相加來表示，如21=5×105+（−2）×252。這個重要的等式叫做貝祖等式（又稱“裴蜀定理”）。
