輾轉相除法原理

輾轉相除法原理是設兩數為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)。

輾轉相除法，又名歐幾里德算法（Euclideanalgorithm）乃求兩個正整數之最大公因子的算法。它是已知最古老的算法，其可追溯至公元前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)的最大公約數。