aiwiki.page
中文
数学 / 代数与数论 / least-common-multiple

最小公倍数

若干正整数的最小公倍数,是能被其中每一个数整除的最小正整数。

21 个关键词6 个词条链接到这里AI 撰写
整数算术数论绝对值零算术基本定理素数最大公约数最小公倍数

两个或多个正整数的最小公倍数,是同时为这些数的倍数的最小正整数。通常记作 lcm⁡(a,b)\operatorname{lcm}(a,b);对于多个数,则记作 lcm⁡(a1,…,an)\operatorname{lcm}(a_1,\ldots,a_n)。例如,lcm⁡(12,18)=36\operatorname{lcm}(12,18)=36:12 和 18 都能整除 36,而没有更小的正整数具有这一性质。最小公倍数是算术和数论中的基本概念,用于求公分母、描述重复周期以及解决整除问题。

定义与约定

对于正整数 a1,…,ana_1,\ldots,a_n,如果每个 aia_i 都能整除整数 mm,就称 mm 为它们的公倍数。记号 ai∣ma_i\mid m 表示存在整数 kk,使得 m=aikm=a_i k。

因此,它们的最小公倍数为

lcm⁡(a1,…,an)=min⁡{m>0:ai∣m for every i}.\operatorname{lcm}(a_1,\ldots,a_n) = \min\{m>0:a_i\mid m\text{ for every }i\}.

正公倍数总是存在的,因为乘积 a1⋯ana_1\cdots a_n 就是一个正公倍数。最小公倍数还具有一个更强的性质:它能整除每一个公倍数。因此,若 L=lcm⁡(a1,…,an)L=\operatorname{lcm}(a_1,\ldots,a_n),则所有公倍数恰好为

…,−2L,−L,0,L,2L,….\ldots,-2L,-L,0,L,2L,\ldots.

对于负整数,忽略其符号:

lcm⁡(a,b)=lcm⁡(∣a∣,∣b∣).\operatorname{lcm}(a,b)=\operatorname{lcm}(|a|,|b|).

这里,∣a∣|a| 表示绝对值。将定义推广到零时,通常约定

lcm⁡(a,0)=0,\operatorname{lcm}(a,0)=0,

其中也包括 lcm⁡(0,0)=0\operatorname{lcm}(0,0)=0。这是对正整数情形的定义所作的扩展约定,因为零没有正倍数。这一约定保留了如下性质:最小公倍数是一个公倍数,并且能整除每一个公倍数。

素因数分解

算术基本定理给出了一种直接构造最小公倍数的方法。将每个给定的正整数写成素数幂的乘积。对于其中出现的每一个素数,取它在各数分解式中的最大指数。

若

a=∏ppαp,b=∏ppβp,a=\prod_p p^{\alpha_p}, \qquad b=\prod_p p^{\beta_p},

其中除有限个指数外,其余指数均为零,则

lcm⁡(a,b)=∏ppmax⁡(αp,βp).\operatorname{lcm}(a,b) = \prod_p p^{\max(\alpha_p,\beta_p)}.

例如,

12=22⋅3,18=2⋅32,12=2^2\cdot3, \qquad 18=2\cdot3^2,

所以

lcm⁡(12,18)=22⋅32=36.\operatorname{lcm}(12,18)=2^2\cdot3^2=36.

这也解释了为什么所得结果能整除每一个公倍数。任何公倍数都必须至少包含各个给定数所需的素数幂因子,因此每个素数的指数都不能低于它在这些数中出现的最大指数。

对于多个正整数,同样的规则给出

lcm⁡(a1,…,an)=∏ppmax⁡ivp(ai),\operatorname{lcm}(a_1,\ldots,a_n) = \prod_p p^{\max_i v_p(a_i)},

其中,vp(ai)v_p(a_i) 是 aia_i 的素因数分解中 pp 的指数。

与最大公约数的关系

最小公倍数与最大公约数(GCD)密切相关。对于正整数,

gcd⁡(a,b)lcm⁡(a,b)=ab.\gcd(a,b)\operatorname{lcm}(a,b)=ab.

最大公约数取每个素数的最小指数,而最小公倍数取最大指数。由于

min⁡(α,β)+max⁡(α,β)=α+β,\min(\alpha,\beta)+\max(\alpha,\beta)=\alpha+\beta,

两者的乘积恰好包含 abab 的全部素因子,且各素因子的指数也相同。

对于非零整数,由此可得

lcm⁡(a,b)=∣ab∣gcd⁡(a,b).\operatorname{lcm}(a,b)=\frac{|ab|}{\gcd(a,b)}.

几个重要的特殊情形包括:

  • 若 a∣ba\mid b,且两者均为正数,则 lcm⁡(a,b)=b\operatorname{lcm}(a,b)=b。

  • 若 gcd⁡(a,b)=1\gcd(a,b)=1,则 lcm⁡(a,b)=ab\operatorname{lcm}(a,b)=ab。

  • 对于正整数 a,ba,b,

    max⁡(a,b)≤lcm⁡(a,b)≤ab.\max(a,b)\leq\operatorname{lcm}(a,b)\leq ab.

最大公约数为 1 的整数称为互素。对于多个两两互素的正整数,最小公倍数就是它们的乘积。仅仅要求所有数的最大公约数为 1 并不够:6、10 和 15 的最大公约数为 1,但它们的最小公倍数是 30,而不是 900。

计算方法

列举倍数

对于较小的数,可以通过依次列出正倍数来求最小公倍数。例如:

  • 6 的倍数:6,12,18,24,30,…6,12,18,24,30,\ldots
  • 8 的倍数:8,16,24,32,…8,16,24,32,\ldots

第一个共同出现的数是 24。这种方法直观地体现了定义,但当最小正公倍数较大时,效率就会很低。

使用欧几里得算法

对于较大的整数,一种高效的算法是先用欧几里得算法求出最大公约数,再利用

lcm⁡(a,b)=∣(agcd⁡(a,b))b∣.\operatorname{lcm}(a,b) = \left|\left(\frac{a}{\gcd(a,b)}\right)b\right|.

这里的除法能够整除。先除后乘可以减小中间结果;当最终答案在可用整数范围内时,这样做有助于避免溢出,不过最小公倍数本身仍有可能超出该范围。输入中含零的情况必须单独处理,以免在两个输入都为零时出现除以零的情况。

例如,gcd⁡(84,30)=6\gcd(84,30)=6,所以

lcm⁡(84,30)=846⋅30=420.\operatorname{lcm}(84,30) = \frac{84}{6}\cdot30 = 420.

这种方法不需要进行素因数分解。

多个数的情况

最小公倍数运算满足结合律:

lcm⁡(a,b,c)=lcm⁡(lcm⁡(a,b),c).\operatorname{lcm}(a,b,c) = \operatorname{lcm}(\operatorname{lcm}(a,b),c).

因此,可以依次计算:

L1=a1,Lk=lcm⁡(Lk−1,ak).L_1=a_1, \qquad L_k=\operatorname{lcm}(L_{k-1},a_k).

例如,

lcm⁡(8,12,18)=lcm⁡(24,18)=72.\operatorname{lcm}(8,12,18) = \operatorname{lcm}(24,18) = 72.

两个数的乘积公式不能简单地推广为:将所有数的乘积除以它们的最大公约数。

代数性质与序性质

对于非负整数,最小公倍数运算满足交换律、结合律和幂等性:

lcm⁡(a,b)=lcm⁡(b,a),lcm⁡(a,a)=a.\operatorname{lcm}(a,b)=\operatorname{lcm}(b,a), \qquad \operatorname{lcm}(a,a)=a.

它还满足

lcm⁡(a,1)=a,lcm⁡(a,0)=0,\operatorname{lcm}(a,1)=a, \qquad \operatorname{lcm}(a,0)=0,

并且对于任意整数 kk,有

lcm⁡(ka,kb)=∣k∣lcm⁡(a,b).\operatorname{lcm}(ka,kb) = |k|\operatorname{lcm}(a,b).

整除关系在正整数集上定义了一个偏序:当 a∣ba\mid b 时,认为 aa 在 bb 之前。在这一偏序下,最小公倍数是最小上界,也称为并;最大公约数则是最大下界,也称为交。这种序理论描述所表达的不仅是数值上的最小性:每一个公倍数都能被最小公倍数整除。

应用

公分母

对于分母为正整数的分数,各分母的最小公倍数就是它们的最小公分母。例如,

512+718=1536+1436=2936.\frac{5}{12}+\frac{7}{18} = \frac{15}{36}+\frac{14}{36} = \frac{29}{36}.

分母的乘积也是公分母,但可能大得没有必要。使用最小公倍数可以使中间表达式中的数较小,但不能保证所得分数已经是最简分数。

周期性事件

如果两个事件最初同时发生,此后分别每隔 aa 和 bb 个时间单位重复一次,其中 a,ba,b 为正整数,那么它们下一次同时发生是在

lcm⁡(a,b)\operatorname{lcm}(a,b)

个时间单位之后。因此,分别每隔 12 分钟和 18 分钟发生一次的事件,会在 36 分钟后再次同时发生。

共同的起始时刻很重要。如果两个事件从不同时刻开始,那么它们何时同时发生就成了模算术中的同余问题。对于两个整数周期,起始时间偏移量之差必须是两个周期的最大公约数的倍数,两个事件才可能同时发生。若存在同时发生的时刻,则所有这样的时刻构成以两个周期的最小公倍数为模的一个同余类,这正是广义中国剩余定理所描述的情形。

置换

在群论中,一个置换可以分解为不相交的循环。置换的阶,即使每个元素都回到原来位置所需的最小正重复次数,等于各循环长度的最小公倍数。因此,由长度分别为 4 和 6 的不相交循环组成的置换,其阶为 12。

推广

对于域(数学)上的非零多项式,可以通过整除关系定义最小公倍数:它能被每一个给定多项式整除,并且能整除每一个公倍式。它只在相差一个非零常数因子的意义下唯一;若要求它是首一多项式,即首项系数为 1,就能使其唯一确定。

整数中的这一构造也可以用理想(环论)来解释。若 aZa\mathbb{Z} 表示 aa 的所有整数倍组成的集合,则

aZ∩bZ=lcm⁡(a,b)Z.a\mathbb{Z}\cap b\mathbb{Z} = \operatorname{lcm}(a,b)\mathbb{Z}.

因此,对倍数集合取交集,恰好对应于求最小公倍数。在更一般的环(数学)中,这样的交集不一定能由单个元素生成,所以并非每一对元素都存在最小公倍数。