輾轉相除法的原理

輾轉相除法的原理是，兩個整數的最大公約數等於其中較小的數和兩數的相除餘數的最大公約數。

補充內容：

輾轉相除法，又名歐幾里德算法乃求兩個正整數之最大公因子的算法，它是已知最古老的算法， 其可追溯至公元前300年前。

輾轉相除法處理大數時非常高效，它需要的步驟不會超過較小數的位數的五倍，加百利拉梅於1844年證明了這點，開創了 計算複雜性理論。

輾轉相除法可以求出特定條件的不定方程的一組整數解，兩個整數的最大公約數是能夠同時整除它們的最大的正整數。