# 最小公倍数

## 与最大公因数之关系

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

## 计算方法

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

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

### 递归计算多个整数的最小公倍数

${\displaystyle a_{1},a_{2},a_{3}}$ 的质因数分解分别为${\displaystyle \prod _{i=1}^{n}p_{i}^{e_{1i}},\prod _{i=1}^{n}p_{i}^{e_{2i}},\prod _{i=1}^{n}p_{i}^{e_{3i}}}$，其中 ${\displaystyle p_{i}}$ 是第 ${\displaystyle i}$ 个质数。

${\displaystyle \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)
{
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

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
ans:=(a*b) div gcd(a,b);
write(ans);
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 GDC(a, b int) int {
if a%b == 0 {
return b
}
return GDC(b, a%b)
}

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


## 应用

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

## 参考来源

• 柯召，孙绮，孙琦. 《数论讲义》. 高等教育出版社. 2005. ISBN 753205473X.
• 阿尔伯特﹒H﹒贝勒著 谈祥柏译. 《数论妙趣：数学女王的盛情款待》. 上海教育出版社. 1998. ISBN 7040091909.