輾轉相除法，也被稱為歐幾里得算法，是一種用於計算兩個非負整數a和b的最大公約數（GCD）的算法。其計算公式為gcd(a,b)=gcd(b,a mod b)，其中mod表示取模運算。這個算法的基本原理是：兩個整數的最大公約數等於其中較小的數和兩數相除餘數的最大公約數。
在算法的執行過程中，輾轉相除法不斷地將較大的數減小，並用較小的數除以兩數相除的餘數，直到其中一個數變為0。此時，另一個非零數就是兩數的最大公約數。這個算法不僅在數學中有廣泛套用，也在計算機科學領域有著重要的地位。
例如，如果要計算252和105的最大公約數，首先用252除以105，得到餘數147。然後用105除以147，得到餘數58。接著用147除以58，得到餘數89。這個過程不斷重複，直到餘數為0。在這個過程中，每次計算的餘數都會逐漸減小，直到找到兩個數的最大公約數。