一、輾轉相除法與更相減損術
1、輾轉相除法。也叫歐幾里德演算法，用輾轉相除法求最大公約數的步驟如下：
（1）：用較大的數m除以較小的數n得到一個商
S和一個餘數
R；（2）：若
R＝0，則n為m，n的最大公約數；若
R0，
則用除數n除以餘數0
R得到一個商
1
S和一個餘數
1
R；（3）：若
1
R＝0，則
1
R為m，n的最大公約數；若
1
R0，則用除數
R除以餘數
1
R得到一個商
2
S和一個餘數
2
R； 依次計算直至
n
R＝0，此時所得到的
1
nR即為所求的最大公約數。
二、更相減損術
我國早期也有求最大公約數問題的演算法，就是更相減損術。在《九章算術》中有更相減損術求最大公約數的'步驟：可半者半之，不可半者，副置分母子之數，以少減多，更相減損，求其等也，以等數約之。
翻譯為：
（1）：任意給出兩個正數；判斷它們是否都是偶數。若是，用2約簡；若不是，執行第二步。
（2）：以較大的數減去較小的數，接著把較小的數與所得的差比較，並以大數減小數。繼續這個操作，直到所得的數相等為止，則這個數（等數）就是所求的最大公約數。
例2 用更相減損術求98與63的最大公約數. 分析：（略）
3、輾轉相除法與更相減損術的區別：
（1）都是求最大公約數的方法，計算上輾轉相除法以除法為主，更相減損術以減法為主，計算次數上輾轉相除法計算次數相對較少，特別當兩個數字大小區別較大時計算次數的區別較明顯。
（2）從結果體現形式來看，輾轉相除法體現結果是以相除餘數為0則得到，而更相減損術則以減數與差相等而得到
