最小公倍数是数论中的一个概念。若有一个数
，可以被另外两个数
、
整除，且大于（或等于）和，则为和的公倍数。和的公倍数有无限个，而所有正的公倍数中，最小的公倍数就叫做最小公倍数。同样地，若干个整数公有的倍数中最小的正整数称为它们的最小公倍数。
整数
的最小公倍数一般记作：![[a_1, a_2, \cdots , a_n]](/media/math_img/2631/c04066d337f0d82ae8d415aa318b7f5697ec86ae.svg)
，或者参照英文记法记作
，其中lcm是英语中“最小公倍数”一词（least common multiple）的首字母缩写。
对分数进行加减运算时，要求两数的分母相同才能计算，故需要通分；标准的计算步骤是将两个分数的分母通分成它们的最小公倍数，然后将通分后的分子相加。
最小公倍数可以通过多种方法得到，最直接的方法是列举法，从小到大列举出其中一个数（如最大数）的倍数，当这个倍数也是另一个数的倍数时，就求得最小公倍数。另一个方法是利用公式 来求解，这时首先要知道它们的最大公因数。而最大公因数可以通过短除法得到。
利用整数的唯一分解定理，还可以用质因数分解法。将每个整数进行质因数分解。对每个质数，在质因数分解的表达式中寻找次数最高的乘幂，最后将所有这些质数乘幂相乘就可以得到最小公倍数。譬如求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)
}