跳到正文
数论 · 第 23 章

最大公因数与最小公倍数

用质因数的指数构造最大公因数和最小公倍数,用辗转相除法把大数对一步步变小,再用裴蜀定理看清两种步长究竟能凑出哪些总数。

你需要先会
在 YouTube 上打开
23.0a0%

用质因数求最大公因数和最小公倍数

在本节中,你将能够 用质因数分解求最大公因数或最小公倍数,并运用“最大公因数 × 最小公倍数 = m × n”。

10 匹马分别用 1,2,…,101, 2, \ldots, 10 分钟跑完一圈。它们什么时候会一起回到起点?在 11 到 1010 的每个公倍数时刻它们都会相遇,第一次就是最小公倍数 25202520。

只要把数写成质数的乘积,所有最大公因数和最小公倍数的问题都会变简单。公共的质因数放在图的中间。最大公因数只保留两个数共有的部分;最小公倍数把所有的都保留下来。

要点:对每个质因数,最大公因数取较低的指数,最小公倍数取较高的指数。较低加较高就是两个指数之和,这正是 gcd⁡(m,n)⋅lcm⁡(m,n)=mn\gcd(m, n) \cdot \operatorname{lcm}(m, n) = mn 的原因。

动手探索先玩,再学公式

24 = 2^3 × 3,36 = 2^2 × 3^2:最大公因数 = 12,最小公倍数 = 72

243622233
公共的质因数在中间。按一个按钮,组成最大公因数或最小公倍数。
公共圆片之积:12。所有圆片之积:72。

24 有 4 个质因数圆片,36 有 4 个;其中 3 个是公共的

认识概念

定义 23.0.1 · 最大公因数

两个或多个非零整数的最大公因数(GCD),是能整除其中每一个数的最大正整数。

它也叫最大公约数(英文也写作 GCF,即 Greatest Common Factor)。这两种叫法意思相同。

定义 23.0.2 · 最小公倍数

两个或多个非零整数的最小公倍数(LCM),是能被其中每一个数整除的最小正整数。

概念 23.0.3 · 用质因数分解求最大公因数和最小公倍数

在 mm 和 nn 的质因数分解中,gcd⁡(m,n)\gcd(m, n) 对每个质因数取较低的指数。

lcm⁡(m,n)\operatorname{lcm}(m, n) 对每个质因数取较高的指数。

例如,24=23⋅324 = 2^{3} \cdot 3,36=22⋅3236 = 2^{2} \cdot 3^{2},所以 gcd⁡(24,36)=22⋅3=12\gcd(24, 36) = 2^{2} \cdot 3 = 12,lcm⁡(24,36)=23⋅32=72\operatorname{lcm}(24, 36) = 2^{3} \cdot 3^{2} = 72。

定理 23.0.4 · 最大公因数 × 最小公倍数

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

gcd⁡(m,n)⋅lcm⁡(m,n)=m⋅n.\gcd(m, n) \cdot \operatorname{lcm}(m, n) = m \cdot n.

定理 23.0.5 · 提取公因数

如果两个数有公因数 cc,那么

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

看例题先预测,再揭晓

例 23.1

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 的最小可能值是多少?

质因数维恩图 (总数在例题最后一步揭晓)

2442322
最大公因数 = 2 × 2 = 4
质数24 中4 中较低较高
23223
31001
公共圆片之积:4。所有圆片之积:24。

最大公因数(24, 4) = 2 × 2 = 4

  1. 1

    因为 a=2ba = 2b,gcd⁡(a,b)=gcd⁡(2b,b)\gcd(a, b) = \gcd(2b, b) 是多少?

    先预测一下:
    点击一个选项,或输入它的字母(A–E)。
在 YouTube 上打开

自己做

习题 23.1.7(补充题)

AMC 12

设 NN 是能被每个小于 77 的正整数整除的第二小的正整数。NN 的各位数字之和是多少?

习题 23.1.8(补充题)

AMC 10

有 1010 匹马,分别叫 Horse 11、Horse 22、…\ldots、Horse 1010。它们的名字来自绕圆形跑道跑一圈所需的分钟数:Horse kk 跑一圈恰好用 kk 分钟。在时刻 00,所有马都在跑道的起点。它们朝同一方向出发,并以各自不变的速度一直绕圆形跑道跑下去。所有 1010 匹马再次同时回到起点的最早时刻 S>0S > 0(单位:分钟)是 S=2520S = 2520。设 T>0T > 0 是至少有 55 匹马再次同时位于起点的最早时刻(单位:分钟)。TT 的各位数字之和是多少?

竞赛角真实竞赛题

习题 23.1.1

AMC 10

设 a,b,ca, 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 的因数?

点击一个选项,或输入它的字母(A–E)。

习题 23.1.4

AMC 10

有多少个正整数有序对 (a,b)(a, b) 满足方程

a⋅b+63=20⋅lcm⁡(a,b)+12⋅gcd⁡(a,b),a \cdot b + 63 = 20 \cdot \operatorname{lcm}(a, b) + 12 \cdot \gcd(a, b),

其中 gcd⁡(a,b)\gcd(a, b) 表示 aa 与 bb 的最大公因数,lcm⁡(a,b)\operatorname{lcm}(a, b) 表示它们的最小公倍数?

习题 23.1.6

AMC 12

设 a,b,ca, b, c 和 dd 是正整数,满足下列所有关系:

abcd=26⋅39⋅57lcm⁡(a,b)=23⋅32⋅53lcm⁡(a,c)=23⋅33⋅53lcm⁡(a,d)=23⋅33⋅53lcm⁡(b,c)=21⋅33⋅52lcm⁡(b,d)=22⋅33⋅52lcm⁡(c,d)=22⋅33⋅52\begin{aligned} abcd &= 2^{6} \cdot 3^{9} \cdot 5^{7} \\ \operatorname{lcm}(a, b) &= 2^{3} \cdot 3^{2} \cdot 5^{3} \\ \operatorname{lcm}(a, c) &= 2^{3} \cdot 3^{3} \cdot 5^{3} \\ \operatorname{lcm}(a, d) &= 2^{3} \cdot 3^{3} \cdot 5^{3} \\ \operatorname{lcm}(b, c) &= 2^{1} \cdot 3^{3} \cdot 5^{2} \\ \operatorname{lcm}(b, d) &= 2^{2} \cdot 3^{3} \cdot 5^{2} \\ \operatorname{lcm}(c, d) &= 2^{2} \cdot 3^{3} \cdot 5^{2} \end{aligned}

gcd⁡(a,b,c,d)\gcd(a, b, c, d) 是多少?

点击一个选项,或输入它的字母(A–E)。

习题 23.1.13(补充题)

AMC 12

有多少个正整数 nn 满足:nn 是 55 的倍数,并且 5!5! 与 nn 的最小公倍数等于 10!10! 与 nn 的最大公因数的 55 倍?

过关检测(第 23.0a 节)

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

gcd⁡(84,120)\gcd(84, 120) 是多少?

2

lcm⁡(84,120)\operatorname{lcm}(84, 120) 是多少?

3

两个正整数的最大公因数是 66,最小公倍数是 180180。其中一个是 3636。另一个是多少?

23.0b0%

辗转相除法

在本节中,你将能够 用反复相减的方法,求大数或含 n 的式子的最大公因数。

gcd⁡(186,92)\gcd(186, 92) 是多少?分解质因数可以,但有更快的办法:从 186186 里减去两次 9292。能同时整除这两个数的数,也一定整除剩下的部分。

从 x×yx \times y 的长方形上切下尽可能大的正方形。剩下的长条和原来的长方形有完全相同的公因数。一直切下去:最后一个正方形的边长就是最大公因数。

同样的技巧也适用于式子。要求 gcd⁡(100+n2, 100+(n+1)2)\gcd(100 + n^{2},\ 100 + (n + 1)^{2}),用一个减去另一个,n2n^{2} 就消失了。

动手探索先玩,再学公式

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

gcd(186, 92)

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

gcd(186, 92)

认识概念

定理 23.0.6 · 辗转相除法

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

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

看例题先预测,再揭晓

例 23.2

AIME

数列 101,104,109,116,…101, 104, 109, 116, \ldots 中的数形如 an=100+n2a_n = 100 + n^{2},其中 n=1,2,3,…n = 1, 2, 3, \ldots 对每个 nn,设 dnd_n 为 ana_n 与 an+1a_{n+1} 的最大公因数。当 nn 取遍所有正整数时,求 dnd_n 的最大值。

欧几里得正方形铺砖 (总数在例题最后一步揭晓)

gcd(40501, 40100)

已经切了 0 个正方形。剩下:一个 40501 × 40100 的长方形。

gcd(40501, 40100)

  1. 1

    an+1−ana_{n+1} - a_n 是多少?

    先预测一下:
在 YouTube 上打开

竞赛角真实竞赛题

习题 23.1.3

AIME

这道题在书中还以 22.1.5 的编号出现。

使 n3+100n^{3} + 100 能被 n+10n + 10 整除的最大正整数 nn 是多少?

习题 23.1.15(补充题)

AMC 10

设 nn 是大于 10001000 且满足

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

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

过关检测(第 23.0b 节)

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

用辗转相除法求 gcd⁡(391,299)\gcd(391, 299)。

2

当 nn 取遍所有正整数时,gcd⁡(n2+1, n+1)\gcd(n^{2} + 1,\ n + 1) 的最大可能值是多少?

3

gcd⁡(212−1, 28−1)\gcd(2^{12} - 1,\ 2^{8} - 1) 是多少?

23.0c0%

裴蜀定理

在本节中,你将能够 用裴蜀定理判断 ax + by 能取到哪些总数。

一枚棋子在 00 处,每次可以向左或向右跳 66 或 1010。它能落在 33 上吗?每跳一次它都停在偶数上,所以不能。

每个总数 6x+10y6x + 10y 都是 gcd⁡(6,10)=2\gcd(6, 10) = 2 的倍数。令人惊喜的是反过来也成立:22 的每一个倍数都能到达。把辗转相除法倒过来做,就能找出跳法。

所以 ax+by=cax + by = c 有整数解,当且仅当 gcd⁡(a,b)\gcd(a, b) 整除 cc。要点:这也能证明两个式子互质。如果它们的某个组合等于 11,它们的最大公因数就一定是 11。

动手探索先玩,再学公式

步长 6 和 10:x·6 + y·10 恰好能到达 gcd = 2 的所有倍数

步长 a6
步长 b10
目标—
−60−40−2002040600
0·6 + 0·10 = 0

棋子在 0·6 + 0·10 = 0。

认识概念

定理 23.0.8 · 裴蜀定理

方程

ax+by=cax + by = c

有整数解 x,yx, y,当且仅当 gcd⁡(a,b)\gcd(a, b) 整除 cc。

竞赛角真实竞赛题

习题 23.1.2

IMO

这道题在书中还以 22.1.4 的编号出现。

证明:对每个自然数 nn,分数 21n+414n+3\dfrac{21n+4}{14n+3} 都是既约分数。

gcd(21n + 4, 14n + 3) 整除 1;n = 1 时步长是 25 和 17。步长 25 和 17:x·25 + y·17 恰好能到达 gcd = 1 的所有倍数

n1
目标—
−60−40−2002040600
0·25 + 0·17 = 0

n = 1 时:a = 25,b = 17。

对两个式子做辗转相除
gcd(21n + 4, 14n + 3) = ? (例题最后一步揭晓)
21n + 4 = 25, 14n + 3 = 17

棋子在 0·25 + 0·17 = 0。

这道题要求写出证明。先在纸上写出你的证明,需要时可以看提示,然后和书面证明对照。

过关检测(第 23.0c 节)

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

存在整数 x,yx, y 使 12x+18y=1512x + 18y = 15 吗?

点击一个选项,或输入它的字母(A–E)。
2

对所有整数 xx 和 yy,12x+42y12x + 42y 的最小正值是多少?

3

一枚棋子从数轴上的 00 出发,每步移动 ±8\pm 8 或 ±14\pm 14。它能落在下面哪个数上?

点击一个选项,或输入它的字母(A–E)。
23.1

练习题

在本节中,你将能够 在更难的竞赛题中综合运用质因数的指数、辗转相除法和裴蜀定理。

现在把它们混在一起。这些题常常同时需要质因数的指数、欧几里得的减法,再加上一点奇偶性分析。每道题都有三条提示,卡住了就看看。

想把本章所有习题放在一页上?打开习题集。

竞赛角真实竞赛题

习题 23.1.5

AMC 10/12

设 aa、bb、cc 是正整数,满足

a14+b15=c210.\frac{a}{14} + \frac{b}{15} = \frac{c}{210}.

下列命题中哪些一定成立?

I. 如果 gcd⁡(a,14)=1\gcd(a, 14) = 1 或 gcd⁡(b,15)=1\gcd(b, 15) = 1(或两者都成立),那么 gcd⁡(c,210)=1\gcd(c, 210) = 1。

II. 如果 gcd⁡(c,210)=1\gcd(c, 210) = 1,那么 gcd⁡(a,14)=1\gcd(a, 14) = 1 或 gcd⁡(b,15)=1\gcd(b, 15) = 1(或两者都成立)。

III. gcd⁡(c,210)=1\gcd(c, 210) = 1 当且仅当 gcd⁡(a,14)=gcd⁡(b,15)=1\gcd(a, 14) = \gcd(b, 15) = 1。

点击一个选项,或输入它的字母(A–E)。

习题 23.1.9(补充题)

AMC 12

设 aa、bb、cc 是正整数,满足

a+b+c=23a + b + c = 23

且

gcd⁡(a,b)+gcd⁡(b,c)+gcd⁡(c,a)=9.\gcd(a, b) + \gcd(b, c) + \gcd(c, a) = 9.

a2+b2+c2a^{2} + b^{2} + c^{2} 所有可能的不同值之和是多少?

习题 23.1.10(补充题)

AMC 12

这道题在书中还以 23.1.7 的编号出现。

设 NN 是能被每个小于 77 的正整数整除的第二小的正整数。NN 的各位数字之和是多少?

习题 23.1.11(补充题)

AMC 12

设 nn 是满足下列条件的最小正整数:nn 能被 2020 整除,n2n^{2} 是完全立方数,n3n^{3} 是完全平方数。nn 有几位数?

习题 23.1.12(补充题)

AMC 12

Mary 选了一个 44 位偶数 nn。她把 nn 的所有因数从左到右按递增顺序写下来:1,2,…,n2,n1, 2, \ldots, \dfrac{n}{2}, n。某一刻,Mary 写下了 nn 的因数 323323。写在 323323 右边的下一个因数,最小可能是多少?

习题 23.1.14(补充题)

AIME

满足 y<x≤100y < x \le 100,且 xy\dfrac{x}{y} 与 x+1y+1\dfrac{x+1}{y+1} 都是整数的正整数有序对 (x,y)(x, y) 有多少个?

习题 23.1.16(补充题)

AIME挑战

考虑由正有理数组成的数列 (ak)k≥1(a_k)_{k \ge 1},定义为 a1=20202021a_1 = \dfrac{2020}{2021},并且对 k≥1k \ge 1,若 ak=mna_k = \dfrac{m}{n},其中 mm 和 nn 是互质的正整数,则

ak+1=m+18n+19.a_{k+1} = \frac{m + 18}{n + 19}.

求所有满足下列条件的正整数 jj 之和:有理数 aja_j 能写成 tt+1\dfrac{t}{t+1} 的形式,其中 tt 是某个正整数。

习题 23.1.17(补充题)

AIME挑战

求有序对 (m,n)(m, n) 的个数,其中 mm 和 nn 是集合 {1,2,…,30}\{1, 2, \ldots, 30\} 中的正整数,并且 2m+12^{m} + 1 与 2n−12^{n} - 1 的最大公因数不是 11。