最小公倍數

最小公倍數數論中的一個概念。若有一個數X,可以被另外兩個數A、B整除,且X大於(或等於)A和B,則X為A和B的公倍數。A和B的公倍數有無限個,而所有的公倍數中,最小的公倍數就叫做最小公倍數。兩個整數公有的倍數稱為它們的公倍數,其中最小的一個正整數稱為它們兩個的最小公倍數。同樣地,若干個整數公有的倍數中最小的正整數稱為它們的最小公倍數。n整數的最小公倍數一般記作:,或者參照英文記法記作,其中lcm是英語中「最小公倍數」一詞(lowest common multiple)的首字母縮寫。

例如,十天干和十二地支的混合稱為一個陰曆,干支循環回歸同一名稱的所需時間,就是1210的最小公倍數,即是60──一個「甲子」。

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

與最大公因數之關係

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

 

計算方法

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

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

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

程式代碼

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

C#

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

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

PASCAL

1
var a,b,ans:integer;
function gcd(a,b:integer):longint;
begin
    if b=0 then gcd:=a
    else gcd:=gcd(b,a mod b ) ;
end;
2
var a,b,ans:integer;
function lcm(a,b:integer):longint;
begin
    readln(a,b );
    ans:=(a*b) div gcd(a,b);
    write(ans);
end;

JAVA

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

應用

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

 

其中分母42就是216的最小公倍數。

參見

參考來源

  • 柯召,孫綺,孫琦. 《數論講義》. 高等教育出版社. 2005. ISBN 753205473X. 
  • 阿爾伯特﹒H﹒貝勒著 談祥柏譯. 《數論妙趣:數學女王的盛情款待》. 上海教育出版社. 1998. ISBN 7040091909.