最大公因子和最小公倍數

尋找的方法

最大公因子 (G.C.D. Greatest Common Divisor 或 H.C.F. Highest Common Factor) 和最小公倍數 (L.C.M. Least Common Multiple) 是素因子分解式 (Prime Factorization) 的其中一個應用，當然求取最大公因子和最小公倍數是不一定利用素因子分解式，但這是處理較大的整數中一個較理想的方法。

方法下述：

　

求最大公因子

把所有目標數字以素因子分解式寫出。

比較各數的素因子，只保留在所有目標數字中皆出現過的素因子，指數則要最小的一個。

若完全沒有一樣的素因子，即最大公因子為 1，亦即互素 (Coprime)。

我們會把 a 和 b 的最大公因子記成 GCD( a, b) 或 (a, b)。

　

求最小公倍數

把所有目標數字以素因子分解式寫出。

比較各數的素因子，凡出現的素因子皆保留，指數則要最大的一個。

我們會把 a 和 b 的最小公倍數記成 LCM( a, b) 或 [a, b]。

　

例子

例 1 ：求 720、1480 的最大公因子和最小公倍數。

720 = (2⁴)*(3³)*(5) ， 1480 = (2³)*(5)*(37)

所以最大公因子是 (2³) = 8，而最小公倍數是 (2⁴)*(3³)*(5)*(37) = 26640。

　

又是例子

例 2：求 1234、2345、3456的最大公因子和最小公倍數。

1234 = (2)*(617) ， 2345 = (5)*(7)*(67) ， 3456 = (2⁷)*(3³)

因沒有一素因子全現於三數中，所以最大公因子為 1，

而最小公倍數為 (2⁷)*(3³)*(5)*(7)*(67)*(617)=5000365440。

　

必然結果

對於最大公因子和最小公倍數，下面的結果必然成立：

任何兩個正整數 a、 b 必然會使 ab = (a,b) * [a,b]

任何三個正整數 a、 b 、c 必然會使

(a, b, c) 不多於 (a, b)，[a, b, c] 不少於 [a, b]

[a, b, c] * (ab, bc, ca) = abc

(a, b, c) * (ab, bc, ca) = (a, b) * (b, c) * (c, a)

重新提示大家，[x,y] 和 (x,y) 分別為 x 和 y 的 最大公因子和最小公倍數。

證明便留給大家來作練習了。

　

參考文獻及網址：

潘承洞；潘承彪  " 最大公約數貿最小公倍數" 自 初等數論, 北京：北京大學出版社, p. 25-43, 1992