1.定義

更相減損術是出自《九章算術》的一種求最大公約數的算法，它原本是為約分而設計的，但它適用于任何需要求最大公約數的場合。

原文是：

可半者半之，不可半者，副置分母、子之數，以少減多，更相減損，求其等也。以等數約之。

白話文譯文：
（如果需要對分數進行約分，那么）可以折半的話，就折半（也就是用2來約分）。如果不可以折半的話，那么就比較分母和分子的大小，用大數減去小數，互相減來減去，一直到減數與差相等為止，用這個相等的數字來約分。

2.步驟

第一步：任意給定兩個正整數；判斷它們是否都是偶數。若是，則用2約簡；若不是則執行第二步。
第二步：以較大的數減較小的數，接著把所得的差與較小的數比較，并以大數減小數。繼續這個操作，直到所得的減數和差相等為止。
則第一步中約掉的若干個2的積與第二步中等數的乘積就是所求的最大公約數。
其中所說的“等數”，就是公約數。求“等數”的辦法是“更相減損”法。

3.例子

3.1 例1 求6和3的最大公約數：

（1）由于3不是偶數，所以執行第二步

（2）6-3=3，3=3，減數與差相等，即3為6和3的最大公約數

3.2 例2 求98和64的最大公約數：

（1）98和64是偶數，所以用2約簡得：49和32。49不是偶數，所以執行第二步。

（2）49-32=17，17<32；

32-17=15，15<17；

17-15=2，2<15；

15-2=13；13>2；

13-2=11，11>2；

11-2=9，9>2；

9-2=7，7>2；

7-2=5，5>2；

5-2=3，3>2；

3-2=1，1<2；

2-1=1，1=1，結束

所以98和64的最大公約數為2*1=2