最大公約數與最小公倍數

參見:質因數

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

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

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

請輸入兩或三個正整數

若發現任何錯誤,請發送電子郵件到[email protected]。在此表示感謝!



如何求最大公約數

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

例如,求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

224 60
 12 30

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

224 60
212 30
36  15
 2  5

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


輾轉相除法(歐幾里德算法)

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

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

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


如何求最小公倍數

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

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


分解質因數法

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

24 = 23 × 3
60 = 22 × 3 × 5

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


短除法

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

224 60
 12 30

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

224 60
212 30
36  15
 2  5

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


公式法

在已經算出整數ab的最大公約數的基礎上,我門可以通過下面的公式來求出它們的最小公倍數:

LCM(a,b) =a × b
GCD(a,b)


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

LCM(24,60) =24 × 60 = 120
12

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

Jimmy Sie(著)
Amanda Huang(譯)

返回頁首

參見:質因數