最大公約數，Highest Common Factor（HCF）。
在求解最大公約數的幾種方法中，輾轉相除法最為出名。輾轉相除法是仍然在使用的歷史最悠久的算法之壹。它首次出現於幾何原本（卷7命題1–2、卷10命題2–3）（大約公元前300年）。
在卷7中用於整數，在卷10中用於線段的長度（也就是所說的實數，但是當時未有實數的概念）。卷10中出現的算法是幾何的，兩段線段a和b的最大公約數是準確測量a和b的最大長度。
這個算法可能並非歐幾裏得發明，而僅僅是將先人的結果編進他的幾何原本。數學家、歷史學家範德瓦爾登認為卷7的內容可能來自畢達哥拉斯學院出身的數學家寫的關於數論的教科書。
輾轉相除法是被大約公元前375年的歐多克斯發現的，但也有可能更早之前就已經存在，因為歐幾裏得和亞裏士多德的這兩位歷史名人著作中都出現了?νθυφα?ρεσι?壹詞（anthyphairesis，意為“輾轉相減”）。
常用結論
在解有關最大公約數、最小公倍數的問題時，常用到以下結論：
1、如果兩個自然數是互質數，那麽它們的最大公約數是1，最小公倍數是這兩個數的乘積。
例如8和9，它們是互質數，所以（8，9）=1，[8，9]=72。
2、如果兩個自然數中，較大數是較小數的倍數，那麽較小數就是這兩個數的最大公約數，較大數就是這兩個數的最小公倍數。
例如18與3，18÷3=6，所以（18，3）=3，[18，3]=18。
3、兩個整數分別除以它們的最大公約數，所得的商是互質數。
例如8和14分別除以它們的最大公約數2，所得的商分別為4和7，那麽4和7是互質數。
4、兩個自然數的最大公約數與它們的最小公倍數的乘積等於這兩個數的乘積。
例如12和16，（12，16）=4，[12，16]=48，有4×48=12×16，即（12，16）× [12，16]=12×16。