最小公倍數

最小公倍數（英語：least common multiple，lcm）是數論中的一個概念。若有一個數$X$，可以被另外兩個數$A$、$B$整除，且$X$同時大於或等於$A$和$B$，則$X$為$A$和$B$的公倍數。$A$和$B$的公倍數有無限個，而所有正的公倍數中，最小的公倍數就叫做最小公倍數。同樣地，若干個整數公有的倍數中最小的正整數稱為它們的最小公倍數。$n$整數$a_{1},a_{2},\cdots ,a_{n}$的最小公倍數一般記作：$[a_{1},a_{2},\cdots ,a_{n}]$，或者參照英文記法記作$\operatorname {lcm} (a_{1},a_{2},\cdots ,a_{n})$。

對分數進行加減運算時，要求兩數的分母相同才能計算，故需要擴分；標準的計算步驟是將兩個分數的分母擴分成它們的最小公倍數，然後將擴分後的分子相加。

與最大公因數之關係

兩個整數的最小公倍數與最大公因數之間有如下的關係：

$\operatorname {lcm} (a,b)={\frac {|a\cdot b|}{\operatorname {gcd} (a,b)}}$

計算方法

最小公倍數可以通過多種方法得到，最直接的方法是列舉法，從小到大列舉出其中一個數（如最大數）的倍數，當這個倍數也是另一個數的倍數時，就求得最小公倍數。另一個方法是利用公式$\operatorname {lcm} (a_{1},a_{2})={\frac {a_{1}a_{2}}{\gcd(a_{1},a_{2})}}$來求解，這時首先要知道它們的最大公因數。而最大公因數可以通過短除法得到。

利用整數的唯一分解定理，還可以用質因數分解法。將每個整數進行質因數分解。對每個質數，在質因數分解的表達式中尋找次數最高的乘冪，最後將所有這些質數乘冪相乘就可以得到最小公倍數。譬如求216、384和210的最小公倍數。對216、384和210來說：

$216=2^{3}\times 3^{3}$，$384=2^{7}\times 3^{1}$，$210=2^{1}\times 3^{1}\times 5^{1}\times 7^{1}$。

其中$2$對應的最高次乘冪為$2^{7}$；$3$對應的最高次乘冪為$3^{3}$；$5$和$7$對應的最高次乘冪分別是$5^{1}$與$7^{1}$。將這些乘冪乘起來，就可以得到最小公倍數：

$[216,384,210]=2^{7}\times 3^{3}\times 5^{1}\times 7^{1}=120960$。

短除法

利用短除法，可以快速計算出多個整數的最小公倍數。

以下為例子:

假設我們要求12、20和42的最小公倍數。

a: 6 |12 18 42

b: 2 3 7

最小公倍數=a×b

因此，12、18和42和最小公倍數=6×2×3×7

所以，6×2×3×7=252，12、18和42的最小公倍數是252

遞歸計算多個整數的最小公倍數

可以遞歸求出多個整數的最小公倍數：欲求 $\operatorname {lcm} (a_{1},...,a_{n})(n\geq 3)$，只需求 $\operatorname {lcm} (a_{1},...,a_{n-2},\operatorname {lcm} (a_{n-1},a_{n}))$。

這利用了性質 $\operatorname {lcm} (a_{1},a_{2},a_{3})=\operatorname {lcm} (\operatorname {lcm} (a_{1},a_{2}),a_{3})$。該性質證明如下：

記 $a_{1},a_{2},a_{3}$ 的質因數分解分別為$\prod _{i=1}^{n}p_{i}^{e_{1i}},\prod _{i=1}^{n}p_{i}^{e_{2i}},\prod _{i=1}^{n}p_{i}^{e_{3i}}$，其中 $p_{i}$ 是第 $i$ 個質數。

那麼根據最小公倍數的定義，$\operatorname {lcm} (a_{1},a_{2},a_{3})=\prod _{i=1}^{n}p_{i}^{\max(e_{1i},e_{2i},e_{3i})}$，

$\operatorname {lcm} (\operatorname {lcm} (a_{1},a_{2}),a_{3})=\operatorname {lcm} (\prod _{i=1}^{n}p_{i}^{\max(e_{1i},e_{2i})},a_{3})=\prod _{i=1}^{n}p_{i}^{\max(\max(e_{1i},e_{2i}),e_{3i})}=\prod _{i=1}^{n}p_{i}^{\max(e_{1i},e_{2i},e_{3i})}$，

證畢。

程式代碼

以下使用輾轉相除法求得最大公因數，之後再求最小公倍數。

C

int GCD(int a, int b) {
	if(b) while((a %= b) && (b %= a));
	return a + b;
}

int LCM(int a, int b) {
	return a * b / GCD(a, b);
}

C++

template<typename T>
T GCD(T a, T b) {
	if (b) while((a %= b) && (b %= a));
	return a + b;
}

template<typename T>
T LCM(T a, T b) {
	return a * b / GCD(a, b);
}

C#

int GCD(int a, int b)
{
	return a % b == 0 ? b : GCD(b, a % b);
}

int LCM(int a, int b)
{
	return a * b / GCD(a, b);
}

Go

func GCD(a, b int) int {
    if b == 0 {
        return a
    }
	return GCD(b, a%b)
}

func LCM(a, b int) int {
	return a * b / GCD(a, b)
}

Java

int GCD(int a, int b) {
	return a % b == 0 ? b : GCD(b, a % b);
}

int LCM(int a, int b) { 
	return a * b / GCD(a, b);
}

Pascal

function gcd(a,b:integer):longint;
begin
    if b=0 then gcd:=a
    else gcd:=gcd(b,a mod b);
end;

function lcm(a,b:integer):longint;
begin
    lcm:=(a*b) div gcd(a,b);
end;

Python

def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)
    
def lcm(a, b):
    return a * b / gcd(a, b)

Ruby

def gcd(a, b)
  b.zero? ? a : gcd(b, a % b)
end

def lcm(a, b)
  a * b / gcd(a, b)
end

Swift

func gcd(_ a: Int, _ b: Int) -> Int {
    return b == 0 ? a : gcd(b, a % b)
}

func lcm(_ a: Int, _ b: Int) -> Int {
    return a * b / gcd(a, b)
}

應用

求最小公倍數是進行分數加減法時的步驟之一。將分母擴分時，會把所有分數的分母擴分為它們的最小公倍數，然後將分子相加。例如：

${2 \over 21}+{1 \over 6}={4 \over 42}+{7 \over 42}={11 \over 42}$

其中分母42就是21與6的最小公倍數。

參見

• 公倍數
• 公因數
• 最大公因數

參考來源

• 柯召，孫綺，孫琦. 《数论讲义》. 高等教育出版社. 2005. ISBN 753205473X. 
• 阿爾伯特·H·貝勒著 談祥柏譯. 《数论妙趣：数学女王的盛情款待》. 上海教育出版社. 1998. ISBN 7040091909.