定义 23.0.1 · 最大公因数
两个或多个非零整数的最大公因数(GCD),是能整除其中每一个数的最大正整数。
它也叫最大公约数(英文也写作 GCF,即 Greatest Common Factor)。这两种叫法意思相同。
用质因数的指数构造最大公因数和最小公倍数,用辗转相除法把大数对一步步变小,再用裴蜀定理看清两种步长究竟能凑出哪些总数。
在本节中,你将能够 用质因数分解求最大公因数或最小公倍数,并运用“最大公因数 × 最小公倍数 = m × n”。
10 匹马分别用 分钟跑完一圈。它们什么时候会一起回到起点?在 到 的每个公倍数时刻它们都会相遇,第一次就是最小公倍数 。
只要把数写成质数的乘积,所有最大公因数和最小公倍数的问题都会变简单。公共的质因数放在图的中间。最大公因数只保留两个数共有的部分;最小公倍数把所有的都保留下来。
要点:对每个质因数,最大公因数取较低的指数,最小公倍数取较高的指数。较低加较高就是两个指数之和,这正是 的原因。
两个或多个非零整数的最大公因数(GCD),是能整除其中每一个数的最大正整数。
它也叫最大公约数(英文也写作 GCF,即 Greatest Common Factor)。这两种叫法意思相同。
两个或多个非零整数的最小公倍数(LCM),是能被其中每一个数整除的最小正整数。
在 和 的质因数分解中, 对每个质因数取较低的指数。
对每个质因数取较高的指数。
例如,,,所以 ,。
两个数的最大公因数与最小公倍数之积,等于这两个数之积:
看某一个质数 ,它在 中的指数是 ,在 中的指数是 。最大公因数得到 ,最小公倍数得到 。因为 ,左边 的幂次等于 中 的幂次。每个质数都是如此。
如果两个数有公因数 ,那么
两个数都乘以 ,就是在两个质因数分解中都加上 的各质因数的指数。每个质因数的较低指数恰好增加了它在 中的指数,所以最大公因数被乘以 。
设 是能被每个小于 的正整数整除的第二小的正整数。 的各位数字之和是多少?
有 匹马,分别叫 Horse 、Horse 、、Horse 。它们的名字来自绕圆形跑道跑一圈所需的分钟数:Horse 跑一圈恰好用 分钟。在时刻 ,所有马都在跑道的起点。它们朝同一方向出发,并以各自不变的速度一直绕圆形跑道跑下去。所有 匹马再次同时回到起点的最早时刻 (单位:分钟)是 。设 是至少有 匹马再次同时位于起点的最早时刻(单位:分钟)。 的各位数字之和是多少?
设 和 是正整数,满足 ,,,且 。下列哪个数一定是 的因数?
有多少个正整数有序对 满足方程
其中 表示 与 的最大公因数, 表示它们的最小公倍数?
设 和 是正整数,满足下列所有关系:
是多少?
有多少个正整数 满足: 是 的倍数,并且 与 的最小公倍数等于 与 的最大公因数的 倍?
在本节中,你将能够 用反复相减的方法,求大数或含 n 的式子的最大公因数。
是多少?分解质因数可以,但有更快的办法:从 里减去两次 。能同时整除这两个数的数,也一定整除剩下的部分。
从 的长方形上切下尽可能大的正方形。剩下的长条和原来的长方形有完全相同的公因数。一直切下去:最后一个正方形的边长就是最大公因数。
同样的技巧也适用于式子。要求 ,用一个减去另一个, 就消失了。
其中 , 是正整数。
如果 整除 和 ,它就整除 。如果 整除 和 ,它就整除 。所以这两对数的公因数完全相同,最大的那个也相同。
反复使用辗转相除法。每用一次都得到两个更小的数,直到它们小到可以直接看出最大公因数。例如
这道题在书中还以 22.1.5 的编号出现。
使 能被 整除的最大正整数 是多少?
设 是大于 且满足
的最小正整数。 的各位数字之和是多少?
在本节中,你将能够 用裴蜀定理判断 ax + by 能取到哪些总数。
一枚棋子在 处,每次可以向左或向右跳 或 。它能落在 上吗?每跳一次它都停在偶数上,所以不能。
每个总数 都是 的倍数。令人惊喜的是反过来也成立: 的每一个倍数都能到达。把辗转相除法倒过来做,就能找出跳法。
所以 有整数解,当且仅当 整除 。要点:这也能证明两个式子互质。如果它们的某个组合等于 ,它们的最大公因数就一定是 。
方程
有整数解 ,当且仅当 整除 。
每个 都是 的倍数,所以 时无解。反过来,把辗转相除法倒过来做,可以把 本身写成 ;再乘以 就得到 。
这道题在书中还以 22.1.4 的编号出现。
证明:对每个自然数 ,分数 都是既约分数。
这道题要求写出证明。先在纸上写出你的证明,需要时可以看提示,然后和书面证明对照。
在本节中,你将能够 在更难的竞赛题中综合运用质因数的指数、辗转相除法和裴蜀定理。
现在把它们混在一起。这些题常常同时需要质因数的指数、欧几里得的减法,再加上一点奇偶性分析。每道题都有三条提示,卡住了就看看。
想把本章所有习题放在一页上?打开习题集。
设 、、 是正整数,满足
下列命题中哪些一定成立?
I. 如果 或 (或两者都成立),那么 。
II. 如果 ,那么 或 (或两者都成立)。
III. 当且仅当 。
设 、、 是正整数,满足
且
所有可能的不同值之和是多少?
这道题在书中还以 23.1.7 的编号出现。
设 是能被每个小于 的正整数整除的第二小的正整数。 的各位数字之和是多少?
设 是满足下列条件的最小正整数: 能被 整除, 是完全立方数, 是完全平方数。 有几位数?
Mary 选了一个 位偶数 。她把 的所有因数从左到右按递增顺序写下来:。某一刻,Mary 写下了 的因数 。写在 右边的下一个因数,最小可能是多少?
满足 ,且 与 都是整数的正整数有序对 有多少个?
考虑由正有理数组成的数列 ,定义为 ,并且对 ,若 ,其中 和 是互质的正整数,则
求所有满足下列条件的正整数 之和:有理数 能写成 的形式,其中 是某个正整数。
求有序对 的个数,其中 和 是集合 中的正整数,并且 与 的最大公因数不是 。