輾轉相除法

在數學中，輾轉相除法，又稱歐幾里得算法，是求最大公因數的算法。輾轉相除法首次出現於歐幾里得的《幾何原本》（第VII卷，命題i和ii）中，而在中國則可以追溯至東漢出現的《九章算術》。兩個整數的最大公因數是能夠同時整除它們的最大的正整數。輾轉相除法基於如下原理：兩個整數的最大公因數等於其中較小的數和兩數的差的最大公因數。例如，252和105的最大公因數是21（252 = 21 × 12；105 = 21 × 5）；因為252 − 105 = 21 × (12 − 5) = 147，所以147和105的最大公因數也是21。在這個過程中，較大的數縮小了，所以繼續進行同樣的計算可以不斷縮小這兩個數直至其中一個變成零。這時，所剩下的還沒有變成零的數就是兩數的最大公因數。由輾轉相除法也可以推出，兩數的最大公因數可以用兩數的整數倍相加來表示，如21 = 5 × 105 + (−2) × 252。這個重要的結論叫做貝祖定理。
輾轉相除法處理大數時非常高效，如果用除法而不是減法實現，它需要的步驟不會超過較小數的位數（十進位下）的五倍。同時這也標誌著計算複雜性理論的開端。