參見：數、質因數

---

最大公約數（最大公因數或最大公約子，英語：Greatest Common Divisor，簡寫為GCD）是幾個自然數公有約數中最大的一個。例如，16和40公約數有：1、2、4、8，其中最大的是8，8就是16和40的最大公約數。找出最大公約數有助於將分數約簡到最簡形式。後面我們將介紹如何找最大公约数。

最小公倍數（英語：Least Common Multiple，簡寫為LCM）是幾個自然數公有公倍數中最小一個。例如，5和6公倍數有：30、60、90、⋯⋯其中最小的是30，30就是5和6的最小公倍數。後面我們將介紹如何找最小公倍數。

你可以用下面的計算器求出兩或三個自然數的最大公約數和最小公倍數。

如何求最大公約數

求最大公約數其實有很多方法，以下將介紹比較常見的三種：

• 分解質因數法
• 短除法
• 輾轉相除法（歐幾里德算法）

例如，求24和60的最大公約數。

分解質因數法

該方法要先將兩數分別分解質因數。怎樣分解質因數，請見質因數分解頁。

24 = 2 × 2 × 2 × 3
60 = 2 × 2 × 3 × 5

找出這兩個數的公有質因數。

24 = 2 × 2 × 2 × 3
60 = 2 × 2 × 3 × 5

它們的公有質因數分別為2，2，3。24和60的最大公約數就是這幾個公有質因數的乘積，也即2 × 2 × 3 = 12.

---

短除法

首先用最小公約數去除這兩個數。24和60的最小公約數是2

2	24 60
	12 30

繼續使用這種方法對所得到的商進行分解，直到所得到的商互質為止

2	24 60
2	12 30
3	6  15
	2  5

將左邊的數字連乘，所得到的乘積就是最大公約數。以上24和60的最大公約數就是2 × 2 × 3 = 12。

---

輾轉相除法（歐幾里德算法）

該方法就是通過將要尋找最大公約數的兩個數字進行重複除法，直到最後得到餘數為0

下面我們就用輾轉相除法來找出24和60的最大公約數

• 用兩數種較小的數去除較大的數，這裡我們就要用24除60，得到商為2，餘數為12。
• 接下來用上一步所得到的餘數去除較小的數，也即12除24，商為2，餘數是0。
• 既然已經得到餘數為0，那麼最後一個除數12，就是我們要找的最大公約數。

下面我們再看一個例子：試找出40和64的最大公約數

• 64 ÷ 40 = 1 ⋯⋯ 24
• 40 ÷ 24 = 1 ⋯⋯ 16
• 24 ÷ 16 = 1 ⋯⋯ 8
• 16 ÷ 8 = 2 ⋯⋯ 0
• 得到餘數為0就以為著我們算到這一步就可以了。我們使用的最後一個餘數是8，因此40和64的最大公約數就是8。

---

如何求最小公倍數

下面介紹幾種比較常用的方法：

• 分解質因數法
• 短除法
• 公式法

例如，求24和60的最小公倍數。

---

分解質因數法

使用該方法尋找最小公倍數，先將這幾個數字分解質因數並寫成冪的形式。怎樣分解質因數，請見質因數分解頁。

24 = 2³ × 3
60 = 2² × 3 × 5

各質因數的最高次冪的乘積就是所要求的最小公倍數。因此，示例中24和60的最小公倍數就是2³ × 3 × 5 = 120.

---

短除法

首先用最小公約數去除這兩個數。24和60的最小公約數是2

2	24 60
	12 30

繼續使用這種方法對所得到的商進行分解，直到所得到的商互質為止

2	24 60
2	12 30
3	6  15
	2  5

將所有的公約數及最後的商相乘，所得積就是最小公倍數。以上24和60的最小公倍數就是2 × 2 × 3 × 2 × 5 = 120.

---

公式法

在已經算出整數a、b的最大公約數的基礎上，我門可以通過下面的公式來求出它們的最小公倍數：

$$\mathrm{LCM}(a,b)=\frac{a\times b}{\mathrm{GCD}(a,b)}$$

回到剛才的例子，我們可以求得24和60的最小公倍數：

$$\mathrm{LCM}(24,60)=\frac{24\times 60}{12}=120$$

當然，如果已經知道最小公倍數，你也可以運用這個方法算出最大公約數。

Jimmy Sie（著）
Amanda Huang（譯）

參見：數、質因數