词汇表

选择左侧的一个关键字...

整除和素数最小公倍数

阅读时间: ~10 min

两个跑步者正在环形跑道上训练。第一个跑步者跑一圈需要60 秒,第二个跑步者跑一圈需要40秒。如果两人同时从起跑线 上出发,他们什么时候会在起跑线上再次相遇?

START 40 80 120 60 120

这个问题实际上不是关于赛道的几何学,也不是关于速度和快慢的,而是关于倍数和整 除的。

第一个选手在60秒、120秒、180秒、240秒等后穿过起跑线,这些只是60。 第二个选手在40秒、80秒、120秒、160秒等后穿过起跑线。两位选手同时第一次回到起 跑线上是在秒之后。

我们找到的是个同时是4060 倍数的最小数,这也被称为最小公倍数或缩写为lcm.

求任意两个数ab最小公倍数,如果a 整除 b, 那么很重要的一点是要认识到b必须具有a 的所有素数因子(外加其它的):

12
60
2
 × 
2
 × 
3
2
 × 
2
 × 
3
 × 
5

这很容易验证:如果一个素数因子整除a,同时a整除 b,那么该素数因子一定整除b

为了找到4060的最小公倍数, 我们首先数需要找到两者 的共有素数因子:

40
=
2
×
2
×
2
×
5
60
=
2
×
2
×
3
×
5

假设X4060的最小公倍数。那么 40整除X,所以2_, _{span.number-ball.small.l-blue}2_,{span.number-ball.small.l-blue}2_和 5_必定是X的素数因子。同理, 60整除X,所以{span.number-ball.small.l-green}2_, 2,和35_必定是_{.m-red}X__的素数因子。

要找到X,我们只需将4060的所有素数因子 组合在一起,但是两边出现相同因子时我们只需要一份:

X  =  2 × 2 × 2 × 3 × 5

我们从这得到X = 120,就像我们看到的上图。注意,如果相同的素数因子出 现多次,如上面的2,我们需要保持两个次数中最大的那个次数(40中的 3次比60中的2次多)。

现在我们有了一个简单的方法来查找两个数字的最小公倍数:

  1. 找出每个数的素数因子。
  2. 将所有数素因子组合起来,但重复出现的只算一次。

我们可以使用相同的方法找到三个或更多数的最小公倍数,如123045

12
=
2
×
2
×
3
30
=
2
×
3
×
5
45
=
3
×
3
×
5

因此12, 3045的最小公倍数是 2 × × 3 × 3 × = 180.

一个特例是质数:两个不同质数的最小公倍数是它们简单的求, 因为它们没 有任何共同的数素因子会被“消去”。

北美是各种各样的蝉群的家园。这些蝉有一种奇特的特性,即它们每隔多年的夏季才出 来繁殖——剩余时间它们在地下度过。

例如,佛罗里达州和密西西比州的蝉每13年出现一次。伊利诺斯州和爱荷华州的蝉只每 17年出现一次。但是没有一种蝉有12年、14年、15年或16年的出现周期。

13和17都是质数 - 这是有充分理由的。想象一下森林里有捕食者杀死了蝉。这些捕食者 也会定期出现,比如每6年出现一次。

现在想象下蝉的出现间隔是每${n}年(${isPrime(n) ? '素数' : '非素数'})。 这两种动物每${lcm(n,6)}年会相遇一次,这就是6和${n}

4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

不同的蝉出现周期长度, 决定了蝉和捕食者相遇的时间。

如果蝉的间隔周期是像13和17这样的质数,这个数字看起来就要大得多。这是因为素数 不与6共有任何因子,所以在计算最小公倍数时,我们不会消去任何重复因子。

当然,蝉不知道素数是什么,但在数百万年的时间里,进化证明了素数周期是最安全的。 捕食者似乎已经随着时间的推移而灭绝,但素数周期仍然存在。