最大公约数和最小公倍数

学科 奥数 教学内容 第 5 讲 最大公约数与最小公倍数 知识网络 1 整数 a 能被整数 b 不为零 整除 数 a 就是数 b 的倍数 数 b 就是数 a 的约数 2 几个数公有的约数 叫做这几个数的公约数 公约数的个数是有限的 其中最大的一 个叫这几个数的最大公约数 若 的最大公约数是 d 则可记为 d 3 几个数公有的倍数 叫做这几个数的公倍数 公倍数可以有无限多个 但其中有一个 最小 这个最小的就叫做这几个数的最小公倍数 若自然数的最小公倍数是 m 则可记为 m 4 最大公约数的性质 1 两个数的最大公约数的约数 都是这两个数的公约数 即 如果 a b d c d 那 么 c a c b 2 两个数分别除以它们的最大公约数 所得的商一定是互质的 即 如果 a b d 那么 a d b d 1 5 最小公倍数的性质 1 两个自然数的最大公约数与最小公倍数的乘积等于这两个数的乘积 即 若 a b d a b m 则 dm ab 且 d m 2 若一个数 c 能同时被两个自然数 a b 整除 那么 c 一定能被这两个数的最小公倍数整 除 或者说 一些数的公倍数一定是这些数的最小公倍数的倍数 即 若 m 而 那么 m N 6 以下两点需要特别注意 l 数 a 是数 b 的倍数 数 b 就是数 a 的约数 它们的最大公约数是 b 最小公倍数是 a 2 若两个数互质 则它们的最大公约数是 1 最小公倍数是它们的积 7 求最大公约数常用的方法有 列举法 分解质因数法 短除法 辗转相除法 8 求最小公倍数常用的方法有 列举法 分解质因数法 短除法 最大公约数法 上述各种方法详见例题 更应注意的是 用共同的方法求最大公约数和最小公倍数的区别 9 最大公约数和最小公倍数之间的关系 设 a b 为两个自然数 则 a b 和 a b 有如下关系 ab a b a b 或 10 如果若干个分数 含整数 都是某个分数的整数倍 那么称这个分数是这若干个分 数的公约数 在所有公约数中最大的一个公约数 称为这若干个分数的最大公约数 求一组分数的最大公约数的方法 l 先将各个分数化为假分数 2 求出各个分数的分母的最小公倍数 a 3 求出各个分数的分子的最大公约数 b 4 即为所求 11 如果某个分数 或整数 同时是若干个分数 含整数 的整数倍 那么称这个分数 是这若干个分数的公倍数 在所有公倍数中最小的一个公倍数 称为这若干个分数的最小 公倍数 求一组分数最小公倍数的方法 1 先将各个分数化为假分数 2 求出各个分数分子的最小公倍数 a 3 求出各个分数分母的最大公约数 b 4 即为所求 重点 难点 用短除法求最大公约数和最小公倍数的区别 1 求 n 个数的最大公约数 1 必须每次都用 n 个数的公因数去除 2 一直除到 n 个数的商互质 但不一定两两互质 3 n 个数的最大公约数即为短除式中所有除数的乘积 2 求 n 个数的最小公倍数 1 必须先用 如果有 n 个数的公因数去除 除到 n 个数没有除去 1 以外的公因数后 再用 n l 个数的公因数去除 除到 n 1 个数没有除 1 以外的公因数后 再用 n 2 个数的公因 数去除 如此继续下去 为保证这一条 每次所用的除数均是质数 2 只要有两个数 被除数 能被同一数整除 就要继续除 一定要除到两个数的商两两 互质为止 3 n 个数的最小公倍数即为短除式中 所有除数和最后两两互质的商的乘积 学法指导 1 在处理涉及两数与两数的最大公约数或者最小公倍数的很多问题中 经常用到的基本 关系是 若两数为 a b 那么其中 因此 a b 有时为了确定起见 可设 a b 对于 很多情形 可以排除 a b 的情形 如上述所示 而只假设 a b 2 在掌握了最大公约数 最小公倍数的有关概念后 把这两个概念连在一起的公式 就显得非常重要 它非常明确地表达了这两个概念之间的关系 表明最大公约数与最小公 倍数之间可以互相转化 这往往是解决有关整数问题的重要工具 3 一般来说 约数总是成对出现的 如 30 的约数有 1 30 2 15 3 10 且每对 中两个约数的积就是自然数本身 4 对一个完全平方数来说 例如 由于它是 6 的平方 所以它有一个约数正好是 6 与 之配对的约数仍是 6 其余的约数配对后 每组中有一个小于 6 的约数 另一个是大于 6 的约数 5 非完全平方数的约数是偶数个 完全平方数的约数是奇数个 6 有关最大公约数与最小公倍数的问题 其叙述方式是多种多样的 在解题时一定要认 真审题 不能简单地在题中看到 最多 就认为是求最大公约数 看到 最少 就认为是 求最小公倍数 7 解答问题一般都有多种解法 请同学们一定选择快捷简便而又适合自己思路的方法 8 为了更好地解决有关最大公约数 最小公倍数的问题 还必须掌握有关整除的知识 经典例题 例 1 已知两个自然数的和是 60 它们的最大公约数与最小公倍数之和是 84 求这两个 自然数各是多少 解答 不妨设这两个自然数为 a b 若 a b m 则 且 1 由题意可知 a b 60 即 所以 又因为 故得知 m 为 60 84 的约数 而 60 84 12 所以 m 只可取 l 2 3 4 6 12 六种可能值 但当 m 取 1 2 3 4 5 6 时均不能满足和 所以 m 仅能取 12 则 60 12 5 若 分别取 2 3 时 则相对应的 a b 值为 24 和 36 答 这两个自然数为 24 和 36 例 2 求 180 840 300 的最大公约数 解答 解法一 根据最大公约数的定义 把三个数分别分解质因数 取出全部公共的质因数 每个公共的质因数取出现的最低次数 把这些公共质因数的乘方相乘即得最大公约数 把 180 840 300 分解质因数 取各公共质因数 2 3 5 出现的最低次数 则 180 840 300 的最大公约数为 解法二 短除法 用三个数的大于 1 的公约数作除数 除到最后三个商互质为止 各除 数相乘之积就是要求的最大公约数 180 840 与 300 的最大公约数为 2 2 3 5 60 例 3 求 68 72 84 的最小公倍数 解答 解法一 根据最小公倍数的定义 把三个数分别分解质因数 取出全部质因数 且各质 因数取出现的最高次数 然后相乘即得最小公倍数 把 68 72 84 分解质因数 取全部质因数 2 3 7 17 出现的最高次数 便得 68 72 84 的最小公倍数为 解法二 应用短除法 先用三个数的大于 1 的公约数去除 除到三个商互质时 再用两 个数的大于 1 的公约数去除 除到三个商两两互质时为止 最后把所有除数及最末的三个 商相乘就得到要求的最小公倍数 68 72 与 84 的最小倍数为 2 2 3 17 6 7 8568 例 4 求 1903 与 2249 的最大公约数 思路剖析 不容易直接看出 1903 与 2249 的大于 1 的公约数 所以可先求 2249 除以 1903 的余数 r 所以 2249 1903 1903 r 如果 1903 不是 r 的倍数 再对 1903 与 r 做除法 然后 把求 1903 与 r 的最大公约数转化为求更小的一对数的最大公约数 这样反复做 直到能求 出最后一对数的最大公约数 它也就是 1903 与 2249 的最大公约数 解答 因为 2249 1903 l 346 所以 2249 1903 1903 346 1 又因为 1903 346 5 173 所以 1903 346 346 173 2 由于 346 173 2 即 346 是 173 的倍数 所以 346 173 173 3 根据 1 2 3 三式可以得到 2249 1903 1903 346 346 173 173 点津 这种通过反复作除法来求最大公约数的方法叫做辗转相除法 在以后的实际计算中 可采 用如下的简写格式 简写格式的步骤为 第一步 把两数写在三条竖线之间 第二步 较大数除以较小数 商写在与较小数相邻那条竖线的外边 商与除数的积写在较 大数的下边 求余数 第三步 如果第二步求出的余数不等于 0 就重复第二步的计算 直到余数是 0 为止 第四步 最后一个非零余数就是原来两数的最大公约数 例 5 有任意 50 个自然数 从中是否可以取出若干个 一个或多个 数 使得取出的这 些数之和恰好是 50 的倍数 说明理由 思路剖析 50 个数太多 我们先从较少的数开始考虑 以便发现问题的本质 如果是两个数 a b 那么从中取数有两种情形 取一个数 取两个数作和 我们考虑 a 与 a b 如果 a 能被 2 整除 那么取 a 就符合要求 如果 a b 能被 2 整除 那么 a 与 b 就符合 要求 如果 a 与 a b 都不能被 2 整除 说明 a 与 a b 都是奇数 于是 a b 与 a 的差是偶数 即 b 是偶数 取 b 就符合要求 总之 对两个数的情形 结论成立 如果是三个数 a b c 那么从中取数有三种情形 取一个数 取两个数作和 取三个数 作和 我们考虑 a a b a b c 如果 a 能被 3 整除 那么取 a 就符合要求 如果 a b 能 被 3 整除 那么取 a 与 b 就符合要求 如果 a b c 能被 3 整除 那么取 a b c 就符合要 求 如果 a a b a b c 都不能被 3 整除 则它们除以 3 所得的余数只能是 1 或 2 因而 必有两个余数相等 这时余数相等的两数之差可被 3 整除 因而仍可取到符合要求的数 总之 对三个数的情形 结论也成立 对多于三个数的情形 可以类似考虑 所以问题能够解决 解答 把原来的 50 个数分别记为 考虑 其中 可以看出 以及它们中间任意两个的差 大减小 都是原来 50 个数中几个数的 和 若 中有一个是 50 的倍数 则取这个数就符合要求 若 中每个数除以 50 所得余数都不等于 0 那么它们分别除以 50 所得的余数只能 是 1 2 3 4 48 49 中的一个 所以至少有两个数 它们被 50 整除 说明仍可取 得符合要求的数 总结以上可知 在 50 个数 中可以找到若干个数 它们的和能被 50 整除 例 6 在一个 30 24 的方格纸上画一条对角线 见图 1 这条对角线除两个端点外 共 经过多少个格点 横线与竖线的交叉点 思路剖析 30 24 6 说明如果将方格纸横 竖都分成 6 份 即分成 6 6 个相同的矩形 那么 每个矩形是由 30 6 24 6 5 4 个 小方格组成 在 6 6 的简化图中 对角线也是它所经过的每一个矩形的对角线 所以经过 5 个格点 见图 2 在对角线所经过的每一个矩形的 5 4 个小方格中 对角线不经过任何 格点 见图 3 解答 对角线共经过格点 30 24 l 5 个 例 7 一张长方形纸 长 2703 厘米 宽 1113 厘米 要把它裁成若干个同样大小的正方 形 纸张不能有剩余且正方形的边长要尽可能大 问 这样的正方形的边长是多少厘米 思路剖析 由题意可知 正方形的边长即是 2703 和 1113 的最大公约数 在学校 我们已经学过用短 除法求两个数的最大公约数 但有时会遇到类似此题情况 两个数除了 1 以外的公约数一 下不好找到 但又不能轻易断定它们是互质数 怎么办 在此 我们以例 7 为例介绍另一 种求最大公约数的方法 对于本题 可做如图 4 的图解 从图 4 中可知 在长 2703 厘米 宽 1113 厘米的长方形纸的一端 依次裁去以宽 1113 厘 米 为边长的正方形 2 个 在裁后剩下的长 1113 厘米 宽 477 厘米的长方形中 再裁去 以宽 477 厘米 为边长的正方形 2 个 然后又在裁剩下的长方形 长 477 厘米 宽 159 厘米 中 以 159 厘米为边长裁正方形 恰好裁成 3 个 且无剩余 因此可知 159 厘米 是 477 厘米 1113 厘米和 2703 厘米的约数 所以裁成同样大的 且边长尽可能长的正方 形的边长应是 159 厘米 所以 159 厘米是 2703 和 1113 的最大公约数 解答 让我们把上述图解过程转化为计算过程 即 2703 1113 商 2 余 477 1113 477 商 2 余 159 477 159 商 3 余 0 或者写为 2703 2 1113 477 1113 2 477 159 477 3 159 当余数为 0 时 最后一个算式中的除数 159 就是原来两个数 2703 和 1113 的最大公约数 可见 477 159 3 1113 159 3 2 159 159 7 2703 159 7 2 477 159 7 2 159 3 159 7 又因为 7 和 17 是互质数 所以 159 是 2703 和 1113 的最大众约数 答 正方形的边长是 159 厘米 例 8 在一间屋子里有 100 盏电灯 排成一行 依从左至右的顺序 编上号码 1 2 3 4 99 100 每盏灯上有一个拉线开关 开始时 全部的灯都关着 有 100 个同学在门外排着队 第 1 个同学进屋把编号是 1 的倍数的所有电灯开关都拉一下即把所 有电灯开关都打开了 接着第二个同学进屋把编号是 2 的倍数的所有电灯开关都拉一下 即把所有编号为偶数的电灯又关上了 第 3 个同学进屋把所有编号是 3 的倍数的电灯开 关都拉一下 如此下去 直到第 100 个同学进屋把第 100 号电灯开关拉了一下 这样做完 以后 问哪些电灯还是亮着的 思路剖析 这道题题目很长 看完后觉得很难下手 我们来分析一下 电灯如果最后是亮的 那么它 一定要被拉奇数次 因为一开一关拉两次是一个周期 拉偶数次的电灯最后一定是关着的 例如 一盏电灯被拉了 4 次 在经历开 关 开 关之后一定是关着的 那么哪些电灯被拉奇数次呢 这取决于它的编号 例如 第 30 号 它是 1 2 3 5 6 10 15 30 的倍数 因此第 l 2 3 5 6 10 15 30 个同学进屋时 都会拉第 30 个电灯 即拉 8 次 因此它最后是关着的 这里不难发现 看一个编号是哪些 数的倍数 其实就是找这个数有哪些约数 约数的个数就代表了电灯被拉的次数 所以 我们只要找出约数个数是奇数的编号就可以知道哪几盏灯是亮的 自然数中只有完全平方数的约数个数是奇数 100 以内的完全平方数有 l 4 9 16 25 36 49 64 81 100 所以编号是这些数的电灯最后是亮着的 解答 由上述分析可知编号是 l 4 9 16 25 36 49 64 81 100 的电灯最后是亮的 例 9 把 1 2 3 4 5 6 7 8 9 这九个数 按照不同的次序排列 可以得到许多 不同的九位数 如 345219876 等等 求所有这些九位数的最大公约数是多少 思路剖析 一个数 如果各数位上的数字之和能被 9 整除 那么这个数一定能被 9 整除 这是能被 9 整除的数的特征 组成的这许多个九位数虽然各不相同 但它们都是由 1 9 这九个数字按 不同的次序排列得到的 每个九位数的各数位之和都是 1 2 3 9 45 9 5 所以每个九 位数都是 9 的倍数 因而 9 是这些九位数的公约数 下面的问题就是研究 9 是不是这些九 位数的最大公约数 现在任取一个九位数 如 123456789 令 12356789 9 a 则比它大 9 的九位数是 123456798 9 a 1 因为 a 与 a l 互质 所以这两个数没有比 9 更大 的公约数了 这说明 所有这些九位数的最大公约数是 9 解答 由上述分析可知 所有这些九位数的最大公约数是 9 例 10 A B 两个数都恰恰只含有质因数 3 和 5 它们的最大公约数是 75 已知 A 有 12 个约数 B 有 10 个约数 那么 A B 两数的和等于多少 思路剖析 要求 A B 两数的和是多少 最好能先求出 A B 的值各为多少 题目只是告诉我们 A B 两数只含有质因数 3 5 且它们的最大公约数为 75 即 A B 两数都含有这个数 且共同 的只有这个数 因 A 有 12 个约数 12 2 6 或 3 4 B 有 10 个约数 10 2 5 若 12 2 6 则它们的共同因数为 与题目相矛盾 舍去 所以 12 取 3 4 2 l 3 l 对于 B 这个数只能取 所以 A 中 5 的指数不能变 所以 解答 10 2 5 12 2 6 舍去 3 4 2 1 3 l 所以 答 A B 两数的和等于 2550 例 11 某厂加工一批零件 每个零件需要一个螺栓 三个螺母 七个螺钉 已知每个工 人每小时可完成 3 个螺栓或 12 个螺母或 18 个螺钉 要想能均衡生产 使每件零件都配上 套 生产这三种零件各需安排多少人 思路剖析 因为这种零件中所需的螺母是螺栓的 3 倍 螺钉是螺栓的 7 倍 所以我们只需先求生产一 个螺栓 一个螺母 一个螺钉配套起来各需的人数 再用生产螺母的人数扩大 3 倍 生产 螺钉的人数扩大 7 倍便可以达到题目要求了 要想顺利进行 必须每小时加工各种零件的个数是 3 12 18 的公倍数 所以我们可以先 求它们的公倍数 再求各种零件所需人数 解答 因为 3 12 18 36 36 3 12 人 36 12 3 9 人 36 18 7 14 人 答 生产螺栓的需 12 人 生产螺母的需 9 人 生产螺钉的需 14 人 发散思维训练 l 老虎和豹进行跳跃比赛 老虎每次跳米 豹每次跳米 它们每秒都又跳一次 比赛途中 从起点开始 每隔米设有一个陷阱 它们之中谁先掉进陷阱 一个掉进陷阱时另一个跳了 多远 2 已知两个自然数的和为 54 它们的最小公倍数与最大公约数的差为 114 求这两个自然 数 3 有甲 乙 丙三种溶液 分别重千克 千克和千克 现要将它们全部分别装入小瓶中 每个小瓶装入液体的重量相同 问 每瓶最多装多少千克 4 甲校和乙校有同样多的同学参加数学竞赛 学校用汽车把学生送往考场 甲校用的汽车 每车坐 15 人 乙校用的汽车 每车坐 13 人 结果甲校比乙校少派一辆汽车 后来每校各 增加一个人参加竞赛 这样两校需要的汽车就一样多了 最后又决定每校再各增加一个人 参加竞赛 乙校又要比甲校多派一辆汽车 问最后两校共有多少人参加竞赛 5 大雪后的一天 小飞和爷爷共同步测一个圆形花圃的周长 他俩的起点和走的方向完全 相同 小飞每步长 48 厘米 爷爷每步长 72 厘米 由于两人脚印有重合 所以各走完一圈 后雪地上只留下 40 个脚印 求花圃的周长 6 甲数有 9 个约数 乙数有 10 个约数 甲 乙两数的最小公倍数是 2800 求甲 乙两数 各是多少 7 一对啮合齿轮 一个有 132 个齿 一个有 48 个齿 其中啮合的任意一对齿从第一次相 接到再次相接 两个齿轮各要转动多少圈 8 有两个油桶 一个容量为 27 升 另一个容量为 15 升 只利用这两个油桶怎样从一个大 油桶中倒出 6 升油来 发散思维训练 1 解 老虎掉进陷阱时与起点的距离应是和的最小整数倍 即和的最小公倍数 米 所以老虎掉进陷阱时跳了 次 同理 豹掉进陷阱时与起点的距离为 米 所以豹掉进陷阱时跳了 次 所以豹先掉进陷阱 它掉进陷阱时 老虎跳了 米 2 解 设这两个自然数分别为 a 与 b a b a b d a 其中 因为 a b 54 所以 于是有 因此 d 是 54 的约数 又因为这两个数的最小公倍数与最大公约数的差为 114 所以 于是有 因此 d 是 114 的约数 故 d 为 54 与 114 的约数 由于 54 114 6 6 的约数有 1 2 3 6 所以 d 可能取 1 2 3 6 这四个值 如果 d l 由 有 又由 有 115 1 115 5 23 但是 1 115 116 54 5 23 28 54 所以 d 1 如果 d 2 由 有 又由 有 58 1 58 2 29 但是 1 58 59 27 2 29 31 27 所以 d 2 如果 d 3 由 有 又由 有 39 l 39 3 13 但是 1 39 40 18 3 13 16 18 所以 d 3 如果 d 6 由 有 又由 有 20 表示成两个互质数的乘积有两种形式 20 l 20 4 5 虽然 1 20 21 9 但是有 4 5 9 所以取 d 6 是合适的 并有 故 a 6 4 24 b 6 5 30 答 这两个自然数为 24 和 30 3 解 如果三种溶液的重量都是整数 那么每瓶装的重量就是三种溶液重量的最大公约数 现在 的问题是三种溶液的重量不是整数 要解决这个问题 可以将重量分别乘以某个数 将分 数化为整数 求出数值后 再除以这个数 为此 先求几个分母的最小公倍数 6 4 9 36 三种溶液的重量都乘以 36 后 变为 150 135 和 80 150 135 80 5 上式说明 若三种溶液分别重 150 千克 135 千克 80 千克 则每瓶最多装 5 千克 可实 际重量是 150 135 80 的 所以每瓶最多装 千克 答 每瓶最多装千克 4 解 原来甲校比乙校少派一辆汽车 各增加一人以后 两校需要的汽车就一样多了 这说明甲 校在没有增加这一人以前恰好坐满了所派的全部汽车 增加的一辆汽车就坐增加的这一人 所以甲校原来参加竞赛的人数是 15 的倍数 后来又各增加一个人 乙校又要多派一辆汽车 这说明在第 次增加人数之前 乙校所派的 车恰好坐满 也就是说 乙校这时的人数是 13 的倍数 即一个 15 的倍数加 1 以后是 13 的 倍数 由此可知 甲乙两校各增加一人后 派车的辆数相等 但甲校有一辆车只坐一个人 而乙 校每车 13 人恰好坐满原来所派的车 可以设想 甲校原来所派的车每车下来两个人坐到增 加的这辆车上去 就会正好跟乙校的情况一样了 即刚好坐满增加的这辆车 因此 原来 甲校的车辆数是 l3 1 l5 13 6 辆 原来每校参赛人数是 15 6 90 人 答 最后甲乙两校共有 184 人参加竞赛 5 解 要想求出花圃的周长 只要求出小飞和爷爷一