Divisibility and PrimesLowest Common Multiples

Two runners are training on a circular racing track. The first runner takes 60 seconds for one lap. The second runner only takes 40 seconds for one lap. If both leave at the same time from the start line, when will they meet again at the start?

This question really isn’t about the geometry of the race track, or about velocity and speed – it is about multiples and divisibility.

The first runner crosses the start line after 60 seconds, 120 seconds, 180 seconds, 240 seconds, and so on. These are simply the multiplesfactors of 60. The second runner crosses the start line after 40 s, 80 s, 120 s, 160 s, and so on. The first time both runners are back at the start line is after seconds.

What we’ve just found is the smallest number which is both a multiple of 40 and a multiple of 60. This is called the lowest common multiple or lcm.

To find the lcm of any two numbers, it is important to realise that if a divides b, then b needs to have all the prime factors of a (plus some more):

This is easy to verify: if a prime factor divides a, and a divides b, then that prime factor must also divide b.

To find the lcm of 40 and 60, we first need to find the prime factorisation of both:

Suppose that X is the lcm of 40 and 60. Then 40 divides X, so 2, 2, 2 and 5 must be prime factors of X. Also, 60 divides X, so 2, 2, 3 and 5 must be prime factors of X.

To find X, we simply combine all the prime factors of 40 and 60, but any duplicates we only need once:

X  =  2 × 2 × 2 × 3 × 5

This gives us that X = 120, just like we saw above. Notice that if the same prime factor appears multiple times, like 2 above, we need to keep the maximum occurrences in one of the two numbers (3 times in 40 is more than 2 times in 60).

Now we have a simple method for finding the lcm of two numbers:

1. Find the prime factorisation of each number.
2. Combine all prime factors, but only count duplicates once.

We can use the same method to find the lcm of three or more numbers at once, like 12, 30 and 45:

Therefore the lcm of 12, 30 and 45 is 2 × × 3 × 3 × = 180.

Prime numbers are a special case: the lcm of two different primes is simply their productsumdifference, because they don’t have any common prime factors which would get “canceled”.

Cicadas

Both 13 and 17 are prime numbers – and that has a very good reason. Imagine that there are predators in the forest which kill cicadas. These predators also appear in regular intervals, say every 6 years.

Now imagine that a brood of cicadas appears every ${n} years (${isPrime(n) ? 'prime' : 'not prime'}). The two animals would meet every ${lcm(n,6)} years, which is the lcmproductaverage of 6 and ${n}.

This number seems to be much larger if the cicada cycle is a prime number like 13 and 17. That’s because prime numbers don’t share any factors with 6, so when calculating the lcm we don’t cancel any duplicate factors.

Of course, cicadas have no idea what prime numbers are – but over millions of years, evolution has worked out that prime cycles are the safest. The predator animal seems to have gone extinct over time, but the prime number cycles remain.