最后更新: 2025-10-15 09:54 查看: 98 次纠错评论(0) 课件开VIP

最小公倍数LCM

##  最小公倍数 (Least Common Multiple，LCM)

> 甲、乙两个齿轮互相啮合, 齿数分别为 $84,36,$ 在转动过程中同时啮合的两齿到下次再同时啮合，甲、乙两个齿轮分别转过多少圈?

这个问题的实质是, 求出一个最小正整数, 它同时为 84,36 的倍数. 在小学学过使用辗转相除法求最小公倍数，如下图
![图片](/uploads/2025-06/d53faf.jpg){width=300px}

但是我们需要一个新的方法来寻求最小公倍数。

事实上, 任给两个非零整数 $a, b$, 一定存在一个整数, 它同时为 $a, b$ 的倍数, 这个倍数叫做 $a, b$ 的**公倍数**. 例如, $|a b|$ 就是 $a, b$ 的一个公倍数.
我们把 $a, b$ 的最小的**正**公倍数叫做 $a, b$ 的**最小公倍数**, 记作 $[a, b]$.
例如, $8,-6$ 的公倍数为 $24,-24,48,-48,72,-72, \cdots$ 其中最小的正公倍数为 $24$ , 因此 $[8,-6]=24$.

类似地, 我们还可以定义三个非零整数或更多个非零整数的最小公倍数的概念, 将非零整数 $a, b$ 和 $c$ 的最小公倍数记作 $[a, b, c]$, 依此类推.

> 下面我们证明两个非零整数 $a, b$ 的最小公倍数 $[a, b]$ 一定整除 $a, b$ 的公倍数.

证明：设 $[a, b]=m$,而 $n$ 为 $a, b$ 的任意一个公倍数.
对 $n, m$ 用带余除法: $n=m q+r(0 \leqslant r<m)$.
假设 $m$ 不能整除 $n$, 则 $r>0$.
由 $a|m, b| m, a|n, b| n$, 得$a|n-m q=r, b| n-m q=r$,
所以 $r$ 也是 $a, b$ 的一个正公倍数, 而 $r<m$, 这与 $m=[a, b]$ 矛盾.
因此, $m \mid n$.

## 最小公倍数性质
我们发现,  最大公约数 $(a, b)$,  最小公倍数$[a, b]$ 和 两数的乘积 $a b$ 之间存在下面的关系:

$$
\boxed {
(a, b)[a, b]=|a b|  ...(1) 
}
$$

上述关系的证明此处略. 详见 [整除理论](https://kb.kmath.cn/kbase/detail.aspx?id=3487)

**由上述关系可知, 可以由两个非零整数乘积的绝对值除以它们的最大公因数求得它们的最小公倍数.**

把公式（1）变形就可以得到

$$
\boxed {
[a, b]=\frac{|a b|}{(a, b)}  ...(2) 
}
$$
或写成
$$
LCM(a, b) = \frac{|a × b|}{GCD(a, b)}
$$

这表明可以利用公约数找到公倍数

`例`求 $[375,105]$ 的值.
解: 因为 $375=105 \times 3+60$,

$$
\begin{aligned}
& 105=60 \times 1+45, \\
& 60=45 \times 1+15, \\
& 45=15 \times 3,
\end{aligned}
$$

所以

$$
(375,105)=15 \text {. }
$$

于是

$$
[375,105]=\frac{375 \times 105}{(375,105)}=2625

类似地，求多个非零整数的最小公倍数，可以转化为求两个非零整数的最小公倍数．例如，$[a, b, c]=[[a, b], c]$ ．

下面是计算机代码的实现

``` 
def gcd(a, b):
    """求最大公约数"""
    while b != 0:
        a, b = b, a % b
    return a

def lcm(a, b):
     return abs(a * b) // gcd(a, b)
```

测试
``` 
print(lcm(12, 18))    # 输出: 36
print(lcm(7, 5))      # 输出: 35
print(lcm(15, 20))    # 输出: 60
```

科数题库(单机版) 会议室预约系统(book)

今日还可看 0 篇未注册用户每天查看4篇，注册用户每天8篇，开通VIP会员无限制查看。

免费注册

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

上一篇：最大公因数GCD

下一篇：算术基本定理

本文对您是否有用？有用 (0) 无用 (0)