两个或多个正整数的最小公倍数,是同时为这些数的倍数的最小正整数。通常记作 lcm(a,b);对于多个数,则记作 lcm(a1,…,an)。例如,lcm(12,18)=36:12 和 18 都能整除 36,而没有更小的正整数具有这一性质。最小公倍数是算术和数论中的基本概念,用于求公分母、描述重复周期以及解决整除问题。
定义与约定
对于正整数 a1,…,an,如果每个 ai 都能整除整数 m,就称 m 为它们的公倍数。记号 ai∣m 表示存在整数 k,使得 m=aik。
因此,它们的最小公倍数为
lcm(a1,…,an)=min{m>0:ai∣m for every i}.
正公倍数总是存在的,因为乘积 a1⋯an 就是一个正公倍数。最小公倍数还具有一个更强的性质:它能整除每一个公倍数。因此,若 L=lcm(a1,…,an),则所有公倍数恰好为
…,−2L,−L,0,L,2L,….
对于负整数,忽略其符号:
lcm(a,b)=lcm(∣a∣,∣b∣).
这里,∣a∣ 表示绝对值。将定义推广到零时,通常约定
lcm(a,0)=0,
其中也包括 lcm(0,0)=0。这是对正整数情形的定义所作的扩展约定,因为零没有正倍数。这一约定保留了如下性质:最小公倍数是一个公倍数,并且能整除每一个公倍数。
素因数分解
算术基本定理给出了一种直接构造最小公倍数的方法。将每个给定的正整数写成素数幂的乘积。对于其中出现的每一个素数,取它在各数分解式中的最大指数。
若
a=p∏pαp,b=p∏pβp,
其中除有限个指数外,其余指数均为零,则
lcm(a,b)=p∏pmax(αp,βp).
例如,
12=22⋅3,18=2⋅32,
所以
lcm(12,18)=22⋅32=36.
这也解释了为什么所得结果能整除每一个公倍数。任何公倍数都必须至少包含各个给定数所需的素数幂因子,因此每个素数的指数都不能低于它在这些数中出现的最大指数。
对于多个正整数,同样的规则给出
lcm(a1,…,an)=p∏pmaxivp(ai),
其中,vp(ai) 是 ai 的素因数分解中 p 的指数。
与最大公约数的关系
最小公倍数与最大公约数(GCD)密切相关。对于正整数,
gcd(a,b)lcm(a,b)=ab.
最大公约数取每个素数的最小指数,而最小公倍数取最大指数。由于
min(α,β)+max(α,β)=α+β,
两者的乘积恰好包含 ab 的全部素因子,且各素因子的指数也相同。
对于非零整数,由此可得
lcm(a,b)=gcd(a,b)∣ab∣.
几个重要的特殊情形包括:
若 a∣b,且两者均为正数,则 lcm(a,b)=b。
若 gcd(a,b)=1,则 lcm(a,b)=ab。
对于正整数 a,b,
max(a,b)≤lcm(a,b)≤ab.
最大公约数为 1 的整数称为互素。对于多个两两互素的正整数,最小公倍数就是它们的乘积。仅仅要求所有数的最大公约数为 1 并不够:6、10 和 15 的最大公约数为 1,但它们的最小公倍数是 30,而不是 900。
计算方法
列举倍数
对于较小的数,可以通过依次列出正倍数来求最小公倍数。例如:
- 6 的倍数:6,12,18,24,30,…
- 8 的倍数:8,16,24,32,…
第一个共同出现的数是 24。这种方法直观地体现了定义,但当最小正公倍数较大时,效率就会很低。
使用欧几里得算法
对于较大的整数,一种高效的算法是先用欧几里得算法求出最大公约数,再利用
lcm(a,b)=(gcd(a,b)a)b.
这里的除法能够整除。先除后乘可以减小中间结果;当最终答案在可用整数范围内时,这样做有助于避免溢出,不过最小公倍数本身仍有可能超出该范围。输入中含零的情况必须单独处理,以免在两个输入都为零时出现除以零的情况。
例如,gcd(84,30)=6,所以
lcm(84,30)=684⋅30=420.
这种方法不需要进行素因数分解。
多个数的情况
最小公倍数运算满足结合律:
lcm(a,b,c)=lcm(lcm(a,b),c).
因此,可以依次计算:
L1=a1,Lk=lcm(Lk−1,ak).
例如,
lcm(8,12,18)=lcm(24,18)=72.
两个数的乘积公式不能简单地推广为:将所有数的乘积除以它们的最大公约数。
代数性质与序性质
对于非负整数,最小公倍数运算满足交换律、结合律和幂等性:
lcm(a,b)=lcm(b,a),lcm(a,a)=a.
它还满足
lcm(a,1)=a,lcm(a,0)=0,
并且对于任意整数 k,有
lcm(ka,kb)=∣k∣lcm(a,b).
整除关系在正整数集上定义了一个偏序:当 a∣b 时,认为 a 在 b 之前。在这一偏序下,最小公倍数是最小上界,也称为并;最大公约数则是最大下界,也称为交。这种序理论描述所表达的不仅是数值上的最小性:每一个公倍数都能被最小公倍数整除。
应用
公分母
对于分母为正整数的分数,各分母的最小公倍数就是它们的最小公分母。例如,
125+187=3615+3614=3629.
分母的乘积也是公分母,但可能大得没有必要。使用最小公倍数可以使中间表达式中的数较小,但不能保证所得分数已经是最简分数。
周期性事件
如果两个事件最初同时发生,此后分别每隔 a 和 b 个时间单位重复一次,其中 a,b 为正整数,那么它们下一次同时发生是在
lcm(a,b)
个时间单位之后。因此,分别每隔 12 分钟和 18 分钟发生一次的事件,会在 36 分钟后再次同时发生。
共同的起始时刻很重要。如果两个事件从不同时刻开始,那么它们何时同时发生就成了模算术中的同余问题。对于两个整数周期,起始时间偏移量之差必须是两个周期的最大公约数的倍数,两个事件才可能同时发生。若存在同时发生的时刻,则所有这样的时刻构成以两个周期的最小公倍数为模的一个同余类,这正是广义中国剩余定理所描述的情形。
置换
在群论中,一个置换可以分解为不相交的循环。置换的阶,即使每个元素都回到原来位置所需的最小正重复次数,等于各循环长度的最小公倍数。因此,由长度分别为 4 和 6 的不相交循环组成的置换,其阶为 12。
推广
对于域(数学)上的非零多项式,可以通过整除关系定义最小公倍数:它能被每一个给定多项式整除,并且能整除每一个公倍式。它只在相差一个非零常数因子的意义下唯一;若要求它是首一多项式,即首项系数为 1,就能使其唯一确定。
整数中的这一构造也可以用理想(环论)来解释。若 aZ 表示 a 的所有整数倍组成的集合,则
aZ∩bZ=lcm(a,b)Z.
因此,对倍数集合取交集,恰好对应于求最小公倍数。在更一般的环(数学)中,这样的交集不一定能由单个元素生成,所以并非每一对元素都存在最小公倍数。