已停用 啟用查詢紀錄
輾轉相除法
zhǎn zhuǎn xiāng chú fǎ
解釋
數學上一種求兩正整數最大公約數的方法。
重編國語辭典
解釋
在數學中，輾轉相除法，又稱歐幾里得算法（Euclidean algorithm），是求最大公約數的算法. 輾轉相除法首次出現於歐幾里得的《幾何原本》（第VII卷，命題i和ii）中，而在中國則可以追溯至東漢出現的《九章算術》. 兩個整數的最大公約數是能夠同時整除它們的最大的正整數. 輾轉相除法基於如下原理：兩個整數的最大公約數等於其中較小的數和兩數相除餘數的最大公約數. 例如，252和105的最大公約數是21；因爲 252 − 105 147 ，所以147和105的最大公約數也是21. 在這個過程中，較大的數縮小了，所以繼續進行同樣的計算可以不斷縮小這兩個數直至餘數爲零. 這時，所剩下的還沒有變成零的數就是兩數的最大公約數. 由輾轉相除法也可以推出，兩數的最大公約數可以用兩數的整數倍相加來表示，如 21 = 5 × 105 + (−2) × 252 . 這個重要的結論叫做貝祖定理. 輾轉相除法最早出現在歐幾里得的《幾何原本》中（大約公元前300年），所以它是現行的算法中歷史最悠久的. 這個算法原先只用來處理自然數和幾何長度（相當於正實數），但在19世紀，輾轉相除法被推廣至其他類型的數...閱讀更多
中文維基百科