輾轉相除法是什麼

歐幾里得算法

輾轉相除法，也被稱爲歐幾里得算法，是一種用於計算兩個非負整數最大公約數的算法。

輾轉相除法的基本原理是，用較大的數除以較小的數，得到餘數。然後用除數除以這個餘數，得到新的餘數。繼續用這個方法，直到餘數爲0。此時的除數就是兩個數的最大公約數。例如，如果要計算3139和2117的最大公約數，可以先用3139除以2117，得到餘數1022。然後用2117除以1022，得到餘數73。繼續這個過程，直到餘數爲0，此時的除數就是最大公約數。