輾轉相除法推導過程如下：
設兩數為a、b(a>b)，用gcd(a,b)表示a，b的最大公約數，r=a(modb)為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就是所求最大公約數。