最小公倍数

<image>

最小公倍数（英语：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的最小公倍数。

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

```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++

```cpp
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#

```csharp
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

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

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

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

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

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

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

### Swift

```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\over21}+{1\over6}={4\over42}+{7\over42}={11\over42}$$

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