整除和素数最小公倍数
两个跑步者正在环形跑道上训练。第一个跑步者__跑一圈需要{.m-blue}60__ 秒,第二个跑步者__跑一圈需要{.m-blue}40__秒。如果两人同时从起跑线 上出发,他们什么时候会在起跑线上再次相遇?
这个问题实际上不是关于赛道的几何学,也不是关于速度和快慢的,而是关于倍数和整 除的。
第一个选手在60秒、120秒、180秒、240秒等后穿过起跑线,这些只是__60__的
我们找到的是个同时是__{.m-green}40__ 和__{.m-blue}60__ 倍数的最小数,这也被称为__最小公倍数__或缩写为__lcm__.
求任意两个数__{.m-yellow}a__和__{.m-blue}b__最小公倍数,如果__{.m-yellow}a__ 整除 b, 那么很重要的一点是要认识到__{.m-blue}b__必须具有__{.m-yellow}a__ 的所有素数因子(外加其它的):
12 | 60 | |
2 × 2 × 3 | 2 × 2 × 3 × 5 |
这很容易验证:如果一个素数因子整除__{.m-yellow}a__,同时__{.m-yellow}a__整除 b,那么该素数因子一定__也__整除__{.m-green}b__。
为了找到__{.m-green}40__和__{.m-blue}60__的最小公倍数, 我们首先数需要找到两者 的共有 数字的__质数分解__是将其写为质数乘积的一种方式。
40 | = | 2 | × | 2 | × | 2 | × | 5 | ||
60 | = | 2 | × | 2 | × | 3 | × | 5 |
假设__{.m-red}X__是__{.m-green}40__和__{.m-blue}60__的最小公倍数。那么 40__整除{.m-red}X__,所以_{span.number-ball.small.l-blue}2_, 2,2_和 5_必定是{.m-red}X__的素数因子。同理,
要找到__{.m-red}X__,我们只需将__{.m-green}40__和__{.m-blue}60__的所有素数因子 组合在一起,但是两边出现相同因子时我们只需要一份:
X = 2 × 2 × 2 × 3 × 5
我们从这得到__{.m-red}X__ = 120,就像我们看到的上图。注意,如果相同的素数因子出 现多次,如上面的2,我们需要保持两个次数中最大的那个次数(40__中的 3次比{.m-blue}60__中的2次多)。
现在我们有了一个简单的方法来查找两个数字的最小公倍数:
- 找出每个数的素数因子。
- 将所有数素因子组合起来,但重复出现的只算一次。
我们可以使用相同的方法找到三个或更多数的最小公倍数,如__{.m-blue}12__、 30__和{.m-yellow}45__:
12 | = | 2 | × | 2 | × | 3 | ||||
30 | = | 2 | × | 3 | × | 5 | ||||
45 | = | 3 | × | 3 | × | 5 |
因此__{.m-blue}12__, 30 和 __{.m-yellow}45__的最小公倍数是 2 ×
一个特例是质数:两个不同质数的最小公倍数是它们简单的求
蝉
北美是各种各样的蝉群的家园。这些蝉有一种奇特的特性,即它们每隔多年的夏季才出 来繁殖——剩余时间它们在地下度过。
例如,佛罗里达州和密西西比州的蝉每13年出现一次。伊利诺斯州和爱荷华州的蝉只每 17年出现一次。但是没有一种蝉有12年、14年、15年或16年的出现周期。
13和17都是质数 - 这是有充分理由的。想象一下森林里有捕食者杀死了蝉。这些捕食者 也会定期出现,比如每6年出现一次。
现在想象下蝉的出现间隔是每
如果蝉的间隔周期是像13和17这样的质数,这个数字看起来就要大得多。这是因为素数 不与6共有任何因子,所以在计算最小公倍数时,我们不会消去任何重复因子。
当然,蝉不知道素数是什么,但在数百万年的时间里,进化证明了素数周期是最安全的。 捕食者似乎已经随着时间的推移而灭绝,但素数周期仍然存在。