世界上最早的算法：輾轉相除法（求兩個自然數最大公約數）

      在數學界，輾轉相除法，又稱歐幾裡得算法，被認為是世界上最早的算法（公元前300年），該算法用于求兩個最大公約數的算法。輾轉相除法首次出現于歐幾裡得的《幾何原本》（第VII卷，命題yⅠ和Ⅱ）中，而在中國則可以追溯至東漢出現的《九章算術》。

    兩個自然數的最大公約數是能夠同時整除它們的最大的正整數。輾轉相除法基于如下原理：兩個整數的最大公約數等于其中較小的數和兩數的相除餘數的最大公約數。例如，1254和390的最大公約數是6（1254 = 6 × 209；390 = 6 × 65）；用這兩個數推導最大公約數的過程如下：

1254 % 390 = 84

 390 % 84 = 54

 84 % 54 = 30

 54 % 30 = 24

 30 % 24 = 6

是以這兩個數的最大公約數是6，這很明顯是遞歸算法

這個算法的證明如下：

設兩數為a、b(b<a），用gcd(a,b）表示a，b的最大公約數，r=a mod b 為a除以b以後的餘數，k為a除以b的商。輾轉相除法即是要證明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)dc，b=nc=ycd，故a與b最大公約數成為cd，而非c，與前面結論沖突】

進而可知gcd(b,r)=c，繼而gcd(a,b)=gcd(b,r）。

PS：這個結論是根據第二步r =(m-kn)c，第一步b =nc   将r帶入gcd(b,r)，得到gcd(nc, (m-kn)c），是以隻有n和m-kn互為素數，b和r的最大公約數才為c

下面給出Java的實作