跳到正文
Mastering
AMC 8
数论 · 第 19 章

最大公因数与最小公倍数

把质因数分一分，就能找到最大的公共因数和最小的公共倍数；再用欧几里得的“切正方形”妙招，更快地求出最大公因数。

这一章讲什么？
你需要先会
在 YouTube 上打开
19.10%

最大公因数与最小公倍数基础

在本节中，你将能够 从两个数的质因数分解求出它们的最大公因数和最小公倍数。

你有 12 颗红珠子和 18 颗蓝珠子。你想做一模一样的手链，并且用完所有珠子。最多能做几条手链？这个数就是最大公因数。

把每个数拆成质因数圆片。两个数共有的圆片放在维恩图的重叠部分。

最大公因数只用公共的圆片。最小公倍数用上所有圆片，但公共的圆片只用一次。

动手探索先玩，再学公式

12 = 2^2 × 3，18 = 2 × 3^2：最大公因数 = 6，最小公倍数 = 36

12182233
公共的质因数在中间。按一个按钮，组成最大公因数或最小公倍数。
公共圆片之积：6。所有圆片之积：36。

12 有 3 个质因数圆片，18 有 3 个；其中 2 个是公共的

认识概念

定义 19.1.1 · 最大公因数

两个或多个整数（不全为零）的最大公因数（GCD），是能整除其中每一个整数的最大正整数。

注： 它也叫最大公约数（英文也写作 GCF，即 Greatest Common Factor），这些叫法常常混用。

定义 19.1.2 · 最小公倍数

两个或多个整数（不全为零）的最小公倍数（LCM），是能被这些数整除的最小正整数。

概念 19.1.3

mm 和 nn 的最大公因数 =gcd⁡(m,n)= \gcd(m, n)，可以这样求：在 mm 和 nn 的质因数分解中，每个质因数取较低的指数。

mm 和 nn 的最小公倍数 =lcm⁡(m,n)= \operatorname{lcm}(m, n)，可以这样求：在 mm 和 nn 的质因数分解中，每个质因数取较高的指数。

看例题先预测，再揭晓

例 19.1

AMC 8

180 和 594 的最小公倍数与 180 和 594 的最大公因数之比是多少？

180 = 2^2 × 3^2 × 5，594 = 2 × 3^3 × 11：最大公因数 = 18，最小公倍数 = 5,940

18059425233311
公共的质因数在中间。按一个按钮，组成最大公因数或最小公倍数。
公共圆片之积：18。所有圆片之积：5940。

180 有 5 个质因数圆片，594 有 5 个；其中 3 个是公共的

  1. 1

    把 180 分解质因数。它含有几个因数 2？

    先预测一下：
在 YouTube 上打开

竞赛角真实竞赛题

习题 19.5.2

AMC 8

aa 和 bb 的最小公倍数是 12，bb 和 cc 的最小公倍数是 15。aa 和 cc 的最小公倍数最小可能是多少？

习题 19.5.3

AIME

有多少个 kk，使得 121212^{12} 是正整数 666^6、888^8 和 kk 的最小公倍数？

过关检测（第 19.1 节）

3 题中答对 2 题即可掌握本节。每题只有一次机会，没有提示。
1

gcd⁡(24,36)\gcd(24, 36) 是多少？

2

lcm⁡(8,12)\operatorname{lcm}(8, 12) 是多少？

3

设 a=23⋅52a = 2^3 \cdot 5^2，b=2⋅54⋅7b = 2 \cdot 5^4 \cdot 7。lcm⁡(a,b)\operatorname{lcm}(a, b) 是多少？

19.20%

最大公因数与最小公倍数之积

在本节中，你将能够 用 最大公因数 × 最小公倍数 = m × n，从四个数中的三个求出第四个。

两个神秘的数乘起来是 1260，它们的最小公倍数是 210。不用知道这两个数是多少，你就能求出它们的最大公因数！

把两个数相乘，每个质因数圆片都被算进去了。公共的圆片被算了两次：每个数各一次。

最大公因数含有一次公共圆片，最小公倍数含有一次所有圆片。合起来，它们含有的圆片和 m×nm \times n 一模一样。

动手探索先玩，再学公式

12 = 2^2 × 3，18 = 2 × 3^2：最大公因数 = 6，最小公倍数 = 36

12182233公共圆片在 12 × 18 中被算了两次
6 × 36 = 216 = 12 × 18
gcd⁡(m,n)×lcm⁡(m,n)=m×n\gcd(m,n) \times \operatorname{lcm}(m,n) = m \times n
公共圆片之积：6。所有圆片之积：36。

最大公因数 × 最小公倍数 = 6 × 36 = 216 = 12 × 18

认识概念

定理 19.2.1

两个数的最大公因数与最小公倍数之积，等于这两个数之积：

gcd⁡(m,n)×lcm⁡(m,n)=m×n\gcd(m, n) \times \operatorname{lcm}(m, n) = m \times n

看例题先预测，再揭晓

例 19.2

设两个数 mm 和 nn 满足 mn=1260mn = 1260，且 LCM⁡(m,n)=210\operatorname{LCM}(m, n) = 210。求 GCD⁡(m,n)\operatorname{GCD}(m, n)。

  1. 1

    你知道了乘积和最小公倍数。哪个恒等式把它们和最大公因数联系起来？

    先预测一下：

自己做

习题 19.5.5（补充题）

Omega Learn

如果 2 个数的最大公因数是 12，这 2 个数的最小公倍数是 240，求这两个数的积。

过关检测（第 19.2 节）

3 题中答对 2 题即可掌握本节。每题只有一次机会，没有提示。
1

如果 2 个数的最大公因数是 12，这 2 个数的最小公倍数是 240，求这两个数的积。

2

两个数的积是 600，它们的最大公因数是 5。它们的最小公倍数是多少？

3

gcd⁡(12,n)=4\gcd(12, n) = 4，lcm⁡(12,n)=48\operatorname{lcm}(12, n) = 48。nn 是多少？

19.30%

最大公因数与最小公倍数的更多性质

在本节中，你将能够 提出公因数，并利用“每个公倍数都是最小公倍数的倍数”这一事实。

红灯每 4 秒闪一次，蓝灯每 6 秒闪一次。它们刚刚同时闪了一下。下一次同时闪是什么时候？再下一次呢？

公倍数是 12、24、36，依此类推。看：它们恰好就是最小公倍数的倍数。

两个数同时乘以同一个 cc，最大公因数和最小公倍数也都乘以 cc。

最后两个例题把最大公因数和最小公倍数的条件变成了关于质因数指数的条件。一次只看一个质数！

动手探索先玩，再学公式

4, 6 的倍数（到 40 为止）：公倍数 12, 24, 36；最小公倍数 = 12

数轴 14
数轴 26
数到40
×4481216202428323640×661218243036
这几条数轴第一次在哪里相遇？

4 和 6 的倍数，到 40 为止。

认识概念

定理 19.3.1

公因数可以提出来：

gcd⁡(ac,bc)=c⋅gcd⁡(a,b)\gcd(ac, bc) = c \cdot \gcd(a, b)

定理 19.3.2

公因数可以提出来：

lcm⁡(ac,bc)=c⋅lcm⁡(a,b)\operatorname{lcm}(ac, bc) = c \cdot \operatorname{lcm}(a, b)

定理 19.3.3

如果一个数能被两个数 aa 和 bb 整除，那么它也能被 lcm⁡(a,b)\operatorname{lcm}(a, b) 整除。

看例题先预测，再揭晓

例 19.3

Omega Learn

设 aa 是能被 15、22 和 176 整除的最小正完全立方数。如果 a=b3a = b^3，求 bb。

  1. 1

    一个数能被 15、22 和 176 整除，就一定能被某一个数整除。是哪个数？

    先预测一下：
在 YouTube 上打开

例 19.5

Omega Learn

3 个数 aa、bb、cc 满足 gcd⁡(a,b)=4\gcd(a, b) = 4，gcd⁡(b,c)=18\gcd(b, c) = 18，lcm⁡(a,c)=144\operatorname{lcm}(a, c) = 144。求 a+ca + c 的值。

4, 18 的倍数（到 120 为止）：公倍数 36, 72, 108；最小公倍数 = 36

数到120
×481624324048566472808896104112120×183672108
这几条数轴第一次在哪里相遇？

4 和 18 的倍数，到 120 为止。

  1. 1

    如果 gcd⁡(a,b)=4\gcd(a, b) = 4，那么 aa 和 bb 一定满足什么？

例 19.6

AMC 12

有多少个正整数 nn 满足：nn 是 5 的倍数，并且 5!5! 与 nn 的最小公倍数等于 10!10! 与 nn 的最大公因数的 5 倍？

  1. 1

    把 5!5! 和 10!10! 写成质因数分解的形式。10!10! 中 2 的指数是多少？

    先预测一下：
在 YouTube 上打开

自己做

习题 19.5.6（补充题）

Omega Learn

两个数 aa 和 bb 满足条件 lcm⁡(gcd⁡(24,a),gcd⁡(a,b))=lcm⁡(gcd⁡(24,b),gcd⁡(a,b))\operatorname{lcm}(\gcd(24, a), \gcd(a, b)) = \operatorname{lcm}(\gcd(24, b), \gcd(a, b))。如果 a=2ba = 2b，a+ba + b 最小可能是多少？

竞赛角真实竞赛题

习题 19.5.1

AMC 10

一家商店里每块糖的价格都是整数美分。Casper 的钱恰好够买 12 块红糖，或 14 块绿糖，或 15 块蓝糖，或 nn 块紫糖。一块紫糖的价格是 20 美分。nn 最小可能是多少？

习题 19.5.4

AMC 10

设 a,b,c,a, b, c, 和 dd 是正整数，满足 gcd⁡(a,b)=24\gcd(a, b) = 24，gcd⁡(b,c)=36\gcd(b, c) = 36，gcd⁡(c,d)=54\gcd(c, d) = 54，且 70<gcd⁡(d,a)<10070 < \gcd(d, a) < 100。下列哪个数一定是 aa 的因数？

（原竞赛题的选项：5、7、11、13、17。）

习题 19.5.8（补充题）

Omega Learn

三个数 aa、bb、cc 满足 gcd⁡(a,b)=20\gcd(a, b) = 20，gcd⁡(b,c)=18\gcd(b, c) = 18，lcm⁡(a,c)=5040\operatorname{lcm}(a, c) = 5040。求 a+ca + c 所有可能值的和。

过关检测（第 19.3 节）

3 题中答对 2 题即可掌握本节。每题只有一次机会，没有提示。
1

用 gcd⁡(ac,bc)=c⋅gcd⁡(a,b)\gcd(ac, bc) = c \cdot \gcd(a, b) 求 gcd⁡(700,1100)\gcd(700, 1100)。

2

用 lcm⁡(ac,bc)=c⋅lcm⁡(a,b)\operatorname{lcm}(ac, bc) = c \cdot \operatorname{lcm}(a, b) 求 lcm⁡(30,45)\operatorname{lcm}(30, 45)。

3

一个数能被 6 整除，也能被 10 整除。它一定还能被的最大的数是多少？

19.40%

辗转相除法

在本节中，你将能够 用大数减去小数，快速求出大数的最大公因数。

把 186 和 92 分解质因数很慢。这里有个更快的妙招：从 186 × 92 的长方形里，不断切出尽可能大的正方形。

任何能同时整除 xx 和 yy 的数，也能整除 x−yx - y。所以从 xx 里减去 yy，最大公因数永远不变。

一直减下去，直到其中一个数变成 0。另一个数就是最大公因数。

动手探索先玩，再学公式

30 × 12 的长方形，已切 0/2 次：gcd(30, 12)；最大公因数 = 6

gcd(30, 12)

已经切了 0 个正方形。剩下：一个 30 × 12 的长方形。

gcd(30, 12)

认识概念

定理 19.4.1 · 辗转相除法

辗转相除法（欧几里得算法）告诉我们：

gcd⁡(x,y)=gcd⁡(x−ky,y)\gcd(x, y) = \gcd(x - ky, y)

其中 x>yx > y，kk 是正整数。

看例题先预测，再揭晓

例 19.4

求 186 和 92 的最大公因数。

186 × 92 的长方形，已切 0/2 次：gcd(186, 92)；最大公因数 = 2

gcd(186, 92)

已经切了 0 个正方形。剩下：一个 186 × 92 的长方形。

gcd(186, 92)

  1. 1

    从 186 里尽可能多地减去 92。还剩多少？

    先预测一下：

竞赛角真实竞赛题

习题 19.5.9（补充题）

AMC 10

设 nn 是大于 1000 且满足

gcd⁡(63,n+120)=21和gcd⁡(n+63,120)=60\gcd(63, n + 120) = 21 \quad\text{和}\quad \gcd(n + 63, 120) = 60

的最小正整数。nn 的各位数字之和是多少？

过关检测（第 19.4 节）

3 题中答对 2 题即可掌握本节。每题只有一次机会，没有提示。
1

用辗转相除法求 gcd⁡(91,35)\gcd(91, 35)。

2

求 gcd⁡(323,391)\gcd(323, 391)。

3

把一个 48×1848 \times 18 的长方形一次又一次地切出尽可能大的正方形，直到什么都不剩。最小的正方形边长是多少？

19.5

练习题

在本节中，你将能够 把最大公因数和最小公倍数的指数计数用在一道难的竞赛题上。

来挑战一道 AIME 题！把它拆成 2 的幂和 5 的幂，分别数一数，再相乘。每道题都有 3 条提示，卡住了就看看吧。

想在一页上看到本章所有的题吗？打开习题集。

竞赛角真实竞赛题

习题 19.5.7（补充题）

AIME

用 [r,s][r, s] 表示正整数 rr 和 ss 的最小公倍数。求满足 [a,b]=1000[a, b] = 1000，[b,c]=2000[b, c] = 2000，[c,a]=2000[c, a] = 2000 的正整数有序三元组 (a,b,c)(a, b, c) 的个数。