輾轉相除法的原理是什麽？
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就是所求最大公約數。
以上的就是關於輾轉相除法的原理是什麽的內容介紹了。