歐幾裡得算法，也叫做輾轉相除法。是偉大的歐幾裡得在《幾何原本》中描述的一種求兩個整數最大公約數的高效算法。是最古老的算法之一。相對應的，中國古代《九章算術》中記載的更相減損術也是求兩個整數最大公約數的方法。但是更相減損術的效率卻沒有歐幾裡得算法的高。
1、歐幾裡得算法
假如要求{234, 78}的最大公約數，只需要如下幾個步驟：
第一步：234/78 = 4（餘數42）
第二步：78/42 = 1（餘數是36）
第三步：42/36 = 1（餘數是6）
第四步：36/6= 6（餘數是0）
此時6就是{234, 78}的最大公約數。因為兩個整數相除後的餘數，在計算機科學中也叫做模，英文mod。上面的步驟就是歐幾裡得算法求最大公約數的過程，用數學語言描述求任意兩個整數{m, n}，約定|m| ≥|n|的最公約數，可以描述為gcd(m, n) = gcd(n，m mod n)。gcd是最大公約數的意思，下面我們用兩種方法來證明歐幾裡得算法。
方法一：代數法
我們要求整數{m, n}，約定|m| ≥ |n|的最大公約數，就是gcd(m, n) = gcd(n, m mod n)，下面開始證明。
{m, n}中有一個數字為0，因為約定了|m| ≥ |n|，所以假設n是0吧。此時gcd(m, n) = m，這一步很好理解。{m, n}中m剛好能被n整除時，gcd(m, n) = n，這個也很好理解。除去上面兩種情況的話，剩下的就是gcd(m, n) = gcd(n, m mod n)直觀來看，有|m mod n| < |n|;設a 是{m, n}的一個公約數，此時令m = ax, n = ay, m mod n = z;m/n 的商為b, 此時m = bn + z;因為a是{m, n}的公約數，m = bn +z;可以推導出z必然能被a整除，否則a是{m, n}的公約數就不成立；因此可以得出{m, n}的公約數必然是{n, m mod n}的公約數，也就是gcd(m, n) = gcd(n, m mod n);依次類推就得到gcd(n, m mod n) = gcd(m mod n, n mod (m mod n))，直到餘數是0為止;然後根據上面第二種情況的出的結論可知輾轉相除到餘數為0時，較小的那個數就是{m, n}的最大公約數，證明完畢。
方法二：圖像法
其實{m, n}兩個數可以看作長方形的兩條邊，m是長， n是寬；AB = n, BC = m，為了直觀，圖中的長方形由若干個邊長為1的正方形組成；為了簡單起見，上圖中m =21, n = 14;只需要用邊長為n的正方形ABFE去覆蓋長方形ABCD，此時FC的長就是m mod n，且 FC一定小於BF;設a是{m, n}的一個公約數，則以a為邊長的正方形必然能夠完全的覆蓋以m和n為長和寬的長方形；如上圖所示，藍色區域的正方形就是邊長為n的正方形，覆蓋完之後，FC就是m mod n；此時再用邊長為 m mod n的正方形去覆蓋長方形EFCD，也就是圖中的綠色區域和黃色區域，本示例中剛好被邊長為FC = 7的正方形完全覆蓋完，因此本示例中的gcd(m, n) = gcd(n, m mod n) = 7；任意兩個數都可以以此類推，在本示例中輾轉第二次剛好覆蓋完，所以輾轉相除法也確實形象；經過上面的直觀說明可以看出，當最後一次輾轉後的整數個正方形剛好能夠完全覆蓋長方形面積的時候，此時該正方形的邊長就是gcd(m, n)，，也就是說gcd(m, n) = gcd(n, m mod n) = gcd(m mod n, n mod (m mod n)), 直到兩數相除餘數為0，此時較小的那個數就是{m, n}的最大公約數，這樣說明不夠直觀地話，看看下圖中相對較複雜的示例。
上圖中的過程用數學語言描述就是gcd(38,16) = gcd(16, 38 mod 16) = gcd(16, 6) = gcd(6, 4) = gcd(4, 2) = 2，證明結束。
2、中華更相減損術
更相減損術也叫做中華更相減損術，是出自《九章算術》的一種求最大公約數的算法。其實理解了歐幾裡得算法的話，它非常簡單。而且就效率而言，歐幾裡得算法的效率更高。但這裡也說明一下更相減損術是怎麼一回事，更相減損術就是任意給定兩個正整數以大的數減小的數，接著把所得的差與較小的數比較，並以其中的大數減小數。繼續這個操作，直到所得的減數和差相等為止。此時減數就是最大公約數。
假設我要求{128，60}的最大公約數，執行如下步驟：
第一步：128 - 60 = 68；
第二步：68 - 60 = 8；
第三步：60 - 8 = 52；
第四步：52 - 8 = 44；
第五步：44 - 8 = 36；
第六步：36 - 8 = 28；
第七步：28 - 8 = 20；
第八步：20 - 8 = 12；
第九步：12- 8 = 4；
第十步：8 - 4 = 4；
此時128和60的最大公約數就是4 。
下面用歐幾裡得算法來求一下128和60的最大公約數：
128/60 = 2 餘數8；
60/8 = 7 餘數4；
8/ 4 = 2餘數0；
此時4就是最大公約數。
對比上面兩種算法發現什麼沒？沒錯，更相減損術多步減法相當於歐幾裡得算法的一部除法。因此歐幾裡得算法效率更高，理解了歐幾裡得算法，更相減損術無需證明即可直觀理解。
3、兩個算法的編程實現
約定m≥n，歐幾裡得算法C語言版：
unsignedintgcd(unsignedint m, unsignedint n){unsignedint rem;while(n > 0){ rem = m % n; m = n; n = rem; }return m;}
如果使用遞歸的話代碼更精簡：
unsignedintgcd(unsignedint m, unsignedint n){n == 0 ? m : gcd(n, m % n)}
歐幾裡得算法python 3版：
defgcd(m, n):return m if n == 0else gcd(n, m % n)
約定m≥n, 更相減損術C語言版：
unsignedintgcd(unsignedint m, unsignedint n){unsignedint rem;while(!(m == n)){if(m > n) { rem = m; m = n; n = rem - n; }else { n = n -m; }return m; }
更相減損術python 3版：
defgcd(m, n):while(m - n != n):a = m - nif a > n: m = aelse: m = n n = a print(n)