最大公约数与最小公倍数

在公考数量关系中，最大公约数和最小公倍数是常考的知识点，通常结合在各种应用题中进行考察，例如周期问题、余数问题等。掌握好这个知识点，对于快速解决某些特定类型的题目至关重要。

一、核心概念

1. 最大公约数 (Greatest Common Divisor, GCD)

定义：最大公约数，也称最大公因数，是指两个或多个整数共有约数中最大的一个。

为了理解这个概念，我们来看一个生活中的例子：

想象一下，你是一位装修师傅，接到一个任务，要用正方形的地砖铺满一块长为36厘米，宽为24厘米的矩形区域。客户要求地砖必须是整块的，不能切割，而且要用的地砖尺寸尽可能大，以显得大气美观。

问题分析：
1. 地砖是正方形的，意味着长和宽相等。
2. 地砖要铺满整个区域且不能切割，说明地砖的边长必须既能整除矩形的长（36厘米），又能整除矩形的宽（24厘米）。
3. 换句话说，地砖的边长必须是36和24的“公约数”。
4. 客户要求地砖尺寸尽可能大，所以我们要找的就是36和24的“最大公约数”。
寻找公约数：
- 36的约数有：1, 2, 3, 4, 6, 9, 12, 18, 36
- 24的约数有：1, 2, 3, 4, 6, 8, 12, 24
- 它们的公约数是：1, 2, 3, 4, 6, 12
确定最大公约数：在这些公约数中，最大的一个是12。所以，你应该选用边长为12厘米的正方形地砖。

求最大公约数的方法

(1) 短除法

将所有数并排，用它们的公约数连续去除，直到所得的商互质（两个数没有除1以外的公约数）为止。将所有除数连乘，得到的积就是最大公约数。

例如，求36和24的最大公约数：

2 | 36  24
--|-------
2 | 18  12
--|-------
3 |  9   6
--|-------
   3   2   (此时3和2互质)

最大公约数 = $2 \times 2 \times 3 = 12$

(2) 辗转相除法（欧几里得算法）

这是一种非常高效的方法，特别适合处理大数字。

原理：两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。

步骤：

用较大的数除以较小的数，得到第一个余数。
若余数不为0，则用上一步的除数除以上一步的余数，得到第二个余数。
重复此过程，直到余数为0。此时，最后一个不为0的余数就是这两个数的最大公约数。

例如，求36和24的最大公约数：

$36 \div 24$ ，商为1，余数为12。
$24 \div 12$ ，商为2，余数为0。
此时余数为0，因此最后一个不为0的余数12即为最大公约数。

2. 最小公倍数 (Least Common Multiple, LCM)

定义：最小公倍数是指两个或多个整数公有的倍数中，除0以外最小的一个。

我们再来看一个生活中的例子：

假设一个公交总站，1路车每隔10分钟发一班，2路车每隔15分钟发一班。两路车在早上6:00同时发车，那么下一次它们同时从总站发车是在什么时候？

问题分析：
1. 1路车的发车时间点是：6:00, 6:10, 6:20, 6:30, 6:40, ... (从6:00开始，经过的时间是10的倍数)
2. 2路车的发车时间点是：6:00, 6:15, 6:30, 6:45, ... (从6:00开始，经过的时间是15的倍数)
3. 要找下一次“同时”发车的时间，就是要找10和15的“公倍数”。
4. “下一次”意味着我们要找的是最小的那个公倍数。
寻找公倍数：
- 10的倍数：10, 20, 30, 40, 50, 60, ...
- 15的倍数：15, 30, 45, 60, 75, ...
- 它们的公倍数是：30, 60, ...
确定最小公倍数：在这些公倍数中，最小的是30。所以，它们下一次同时发车是在6:00之后的30分钟，也就是6:30。

求最小公倍数的方法

(1) 短除法

与求最大公约数类似，但最后要把所有的除数和最后的商都连乘起来。

例如，求10和15的最小公倍数：

5 | 10  15
--|-------
   2   3

最小公倍数 = $5 \times 2 \times 3 = 30$

(2) 分解质因数法

与求最大公约数时取“最低次幂”相反，求最小公倍数是取每个质因数的最高次幂进行连乘。

公式：对于任意数 $a, b$ ，其质因数分解为 $a = p_1^{a_1} p_2^{a_2} \dots$ 和 $b = p_1^{b_1} p_2^{b_2} \dots$ 。
$LCM(a,b) = p_1^{\max(a_1,b_1)} \times p_2^{\max(a_2,b_2)} \times \dots$

例：求 12 和 30 的最小公倍数。

分解质因数：
- $12 = 2^2 \times 3^1$
- $30 = 2^1 \times 3^1 \times 5^1$
取各质因数的最高次幂：
- 对于质因数2，最高次幂是 $2^2$ 。
- 对于质因数3，最高次幂是 $3^1$ 。
- 对于质因数5，最高次幂是 $5^1$ 。
连乘： $LCM(12, 30) = 2^2 \times 3^1 \times 5^1 = 4 \times 3 \times 5 = 60$

(3) 较大数翻倍法（快速口算）

这是一种在数字不大时非常实用的心算技巧。

步骤：

找出数字中的最大数。
将这个最大数依次乘以1, 2, 3, ...
每得到一个积，就判断它是否能被所有其他数字整除。
第一个能被所有其他数字整除的积，就是最小公倍数。

例：求 8, 12, 24 的最小公倍数。

最大数是24。
$24 \times 1 = 24$ 。24能被8整除，也能被12整除。
因此，最小公倍数就是24。

例：求 12, 18, 30 的最小公倍数。

最大数是30。
$30 \times 1 = 30$ (不能被12, 18整除)
$30 \times 2 = 60$ (不能被18整除)
$30 \times 3 = 90$ (不能被12整除)
$30 \times 4 = 120$ (不能被18整除)
$30 \times 5 = 150$ (不能被12, 18整除)
$30 \times 6 = 180$ (能被12和18整除, $180 \div 12=15$ , $180 \div 18 = 10$ )
因此，最小公倍数是180。

(4) 公式法

公式：两个数的最小公倍数 = (这两个数的乘积) / (这两个数的最大公约数)

公式推导：这个重要公式的理解，建立在质因数分解之上。任何一个正整数都可以被分解为一串质数的乘积。

我们以数字12和18为例：

$12 = 2^2 \times 3^1$
$18 = 2^1 \times 3^2$

求最大公约数（GCD）时，我们取每个公共质因数的最低次幂相乘： $GCD(12, 18) = 2^{\min(2,1)} \times 3^{\min(1,2)} = 2^1 \times 3^1 = 6$

求最小公倍数（LCM）时，我们取每个质因数的最高次幂相乘（包括非公共的质因数）： $LCM(12, 18) = 2^{\max(2,1)} \times 3^{\max(1,2)} = 2^2 \times 3^2 = 4 \times 9 = 36$

现在，我们来验证公式 $a \times b = GCD(a, b) \times LCM(a, b)$ ：

左边： $12 \times 18 = 216$
右边： $GCD(12, 18) \times LCM(12, 18) = 6 \times 36 = 216$

两边相等，公式成立。这个原理适用于所有正整数。对于任意两个数 $x, y$ ，因为 $\min(x,y) + \max(x,y) = x+y$ 恒成立，所以将所有质因数的次幂相加，最终会得到两个数本身的乘积。

二、真题讲解

主题1：周期性问题

例1：甲、乙、丙三名运动员在环形跑道上练习长跑，他们从同一起点、同一方向同时出发。甲跑一圈需要3分钟，乙跑一圈需要4分钟，丙跑一圈需要5分钟。请问，至少需要多少分钟，三人才能首次在起点相遇？

A. 12
B. 20
C. 60
D. 80

例2：日期问题（2018年省考）

题目：某部门每隔 2 天（即每 3 天）发布一次消息，另一部门每隔 3 天（即每 4 天）发布一次。若两部门在 1 号同时发布，问该月最多有几天同时发布？

A. 1
B. 2
C. 3
D. 4

例3：多目标周期问题（2020年国考真题变式） 题目：四个部门的员工因项目需要定期开会，一部门每6天开一次，二部门每12天开一次，三部门每18天开一次，四部门每30天开一次。如果他们在某月1日同时开会，那么至少再过多少天他们会再次同时开会？

A. 90
B. 120
C. 180
D. 360

主题2：资源分配与裁剪问题

例2：有一批长方形的铁皮，长120厘米，宽90厘米。要将它们裁剪成同样大小、面积尽可能大的正方形铁皮，且没有剩余。请问，可以裁剪出多少块这样的正方形铁皮？

A. 10
B. 12
C. 30
D. 120

主题3：余数问题

例3：有一个正整数，用它除以3余2，除以4余3，除以5余4。这个数最小是多少？

A. 29
B. 59
C. 89
D. 119

主题4：工程问题应用

例4：工程问题（2022年联考）

题目：一项工作甲单独完成需 16 小时，乙需 12 小时，现按甲 1 小时→乙 1 小时的顺序轮流工作，问完成需多少时间？

A. 13小时30分钟
B. 13小时45分钟
C. 14小时
D. 14小时15分钟

三、技巧总结

识别题型是关键
- 求最大公约数 (GCD)：题干中通常包含“分割”、“分配”、“裁剪”、“分组”等词语，要求将一个大的东西分成若干个相等的、尺寸最大的小部分，且没有剩余。例如铺地砖、分水果。
- 求最小公倍数 (LCM)：题干中通常包含“同时发生”、“再次相遇”、“至少需要”等词语，描述几个具有不同周期的事件，问下一次同时发生的时间或数量。例如公交车发车、运动员跑圈。
掌握核心公式
- 对于两个数 $a$ 和 $b$ ，它们之间有一个非常重要的关系： $a \times b = GCD(a, b) \times LCM(a, b)$
- 这个公式在某些题目中可以简化计算，知道其中三个量就可以求出第四个。
余数问题的转化思想
- 同余问题：一个数除以几个不同的数，得到的余数相同。即 $N \div a$ $N \div a$ 余 $k$ $k$ ， $N \div b$ $N \div b$ 余 $k$ $k$ 。
  - 结论：这个数可以表示为 $N = m \times LCM(a, b) + k$ (其中m为非负整数)。最小的数就是 $LCM(a, b) + k$ 。
- 同差问题（本卷例3）：一个数除以几个不同的数，得到的余数与除数的差相同。即 $N \div a$ $N \div a$ 余 $a-k$ $a - k$ ， $N \div b$ $N \div b$ 余 $b-k$ $b - k$ 。
  - 结论：这个数可以表示为 $N = m \times LCM(a, b) - k$ (其中m为正整数)。最小的数就是 $LCM(a, b) - k$ 。

通过掌握以上核心概念和解题技巧，并辅以真题练习，相信你能轻松攻克公考中的最大公约数和最小公倍数问题。

🎯 扫码练一练

AI刷题，天下无敌；上岸在手，编制我有！

🤖 上岸小助手

• 24小时在线答疑
• 个性化学习指导
• 最新考试资讯

质数合数基础数列