輾轉相除法一般指歐幾里得算法。歐幾里得算法又稱輾轉相除法，是指用於計算兩個非負整數a，b的最大公約數。那麼輾轉相除法的原理是什麼？
1、原理：設兩數爲a、b(ab)，用gcd(a，b)表示a，b的最大公約數，r=a(mod b)爲a除以b的餘數，k爲a除以b的商，即a÷b=k。。。。。。。r。輾轉相除法即是要證明gcd(a，b)=gcd(b，r)。
2、第一步：令c=gcd(a，b)，則設a=mc，b=nc。
3、第二步：根據前提可知r=a-kb=mc-knc=(m-kn)c。
4、第三步：根據第二步結果可知c也是r的因數。
5、第四步：可以斷定m-kn與n互質(假設m-kn=xd，n=yd(d1)，則m=kn+xd=kyd+xd=(ky+x)d，則a=mc=(ky+x)cd，b=nc=ycd，則a與b的一個公約數cdc，故c非a與b的最大公約數，與前面結論矛盾)，因此c也是b與r的最大公約數。
6、從而可知gcd(b，r)=c，繼而gcd(a，b)=gcd(b，r)。
7、證畢。以上步驟的操作是建立在剛開始時r≠0的基礎之上的。即m與n亦互質。
8、解釋：輾轉相除法，又名歐幾里德算法（Euclidean algorithm）乃求兩個正整數之最大公因子的算法。它是已知最古老的算法，其可追溯至公元前300年前。
9、來源：設兩數爲a、b(ab)，求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)的最大公約數。
10、例如：a=25，b=15，a/b=1。。。。。.10，b/10=1。。。。。.5，10/5=2。。。。。。.0，最後一個餘數爲0d的除數就是5， 5就是所求最大公約數。
以上的就是關於輾轉相除法的原理是什麼的內容介紹了。
