最小公倍數

最小公倍數是数论中的一个概念。若有一個數，可以被另外兩個數、整除，且大於（或等于）和，則為和的公倍數。和的公倍數有無限個，而所有正的公倍數中，最小的公倍數就叫做最小公倍數。同样地，若干个整数公有的倍数中最小的正整数称为它们的最小公倍数。整数的最小公倍数一般记作：，或者参照英文记法记作，其中lcm是英语中“最小公倍数”一词（least common multiple）的首字母缩写。

对分數进行加減运算時，要求兩數的分母相同才能計算，故需要-{zh-hans:通分; zh-hant:擴分;}-；标准的计算步骤是将兩個分數的分母-{zh-hans:通分; zh-hant:擴分;}-成它们的最小公倍數，然后将-{zh-hans:通分; zh-hant:擴分;}-后的分子相加。

与最大公因数之关系 
两个整数的最小公倍数与最大公因数之间有如下的关系：

计算方法 
最小公倍数可以通过多种方法得到，最直接的方法是列举法，从小到大列举出其中一个数（如最大數）的倍数，当这个倍数也是另一个数的倍数时，就求得最小公倍数。另一个方法是利用公式来求解，这时首先要知道它们的最大公因数。而最大公因数可以通过短除法得到。

利用整数的唯一分解定理，还可以用質因數分解法。将每个整数进行质因数分解。对每个质数，在质因数分解的表达式中寻找次数最高的乘幂，最后将所有这些质数乘幂相乘就可以得到最小公倍数。譬如求216、384和210的最小公倍數。对216、384和210来说：
，，。
其中对应的最高次乘幂为；对应的最高次乘幂为；和对应的最高次乘幂分别是与。将这些乘幂乘起来，就可以得到最小公倍数：
。

递归计算多个整数的最小公倍数 
可以递归求出多个整数的最小公倍数：欲求 ，只需求 。

这利用了性质 。该性质证明如下：

记  的质因数分解分别为，其中  是第  个质数。

那么根据最小公倍数的定义，，

，

证毕。

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

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

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

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

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

def lcm(a, b)
  a * b / 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)

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

应用 
求最小公倍数是进行分数加减法时的步骤之一。将分母-{zh-hans:通分; zh-hant:擴分;}-时，会把所有分数的分母-{zh-hans:通分; zh-hant:擴分;}-为它们的最小公倍数，然后将分子相加。例如：

其中分母42就是21与6的最小公倍数。

参见 
 公倍数
 公因数
 最大公因数

参考来源 
 
 

四则运算
数字运算
数论