歐幾里得算法，也被稱為輾轉相除法，是一種用於計算兩個非負整數a和b的最大公約數(GCD)的算法。其計算公式為gcd(a,b)=gcd(b,a mod b)。該算法的基本思想是通過反覆套用整數除法來找到兩個整數的最大公約數。
算法的原理是，假設我們有兩個正整數a和b，其中a>b。我們的目標是找到它們的最大公約數，即能夠整除a和b的最大正整數。首先，我們用b去除a，得到餘數r。然後，我們將b替換為a，將r替換為b。接著，我們再次用新的b去除新的a，得到新的餘數。我們重複這個過程，直到餘數為0為止。當餘數為0時，前一個非零餘數就是a和b的最大公約數。
這個算法的關鍵在於，每一次疊代都將a和b替換為新的數值，直到最終得到的餘數為0。最後一次非零餘數即為最大公約數。