跳至內容

最小公倍數

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

最小公倍數(英語:least common multiple,lcm)是數論中的一個概念。若有一個數,可以被另外兩個數整除,且同時大於或等於,則公倍數的公倍數有無限個,而所有正的公倍數中,最小的公倍數就叫做最小公倍數。同樣地,若干個整數公有的倍數中最小的正整數稱為它們的最小公倍數。整數的最小公倍數一般記作:,或者參照英文記法記作

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

與最大公因數之關係

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

計算方法

最小公倍數可以通過多種方法得到,最直接的方法是列舉法,從小到大列舉出其中一個數(如最大數)的倍數,當這個倍數也是另一個數的倍數時,就求得最小公倍數。另一個方法是利用公式來求解,這時首先要知道它們的最大公因數。而最大公因數可以通過短除法得到。

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

其中對應的最高次乘冪為對應的最高次乘冪為對應的最高次乘冪分別是。將這些乘冪乘起來,就可以得到最小公倍數:

短除法

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

以下為例子:

假設我們要求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

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

可以遞歸求出多個整數的最小公倍數:欲求 ,只需求

這利用了性質 。該性質證明如下:

的質因數分解分別為,其中 是第 個質數。

那麼根據最小公倍數的定義,

證畢。

程式代碼

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

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)
}

應用

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

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

參見

參考來源

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