# 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 60s, 120s, 180s, 240s, and so on. These are simply the **60**. The second runner crosses the start line after 40s, 80s, 120s, 160s, and so on. The first time both runners are back at the start line is after

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):

12 | 60 | |

2 × 2 × 3 | 2 × 2 × 3 × 5 |

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

40 | = | 2 | × | 2 | × | 2 | × | 5 | ||

60 | = | 2 | × | 2 | × | 3 | × | 5 |

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:

- Find the prime factorisation of each number.
- 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**:

12 | = | 2 | × | 2 | × | 3 | ||||

30 | = | 2 | × | 3 | × | 5 | ||||

45 | = | 3 | × | 3 | × | 5 |

Therefore the lcm of **12**, **30** and **45** is 2 ×

A special case are prime numbers: the lcm of two different primes is simply their

## Cicadas

North America is home to various broods of cicadas. These have the curious property that they only emerge every few years during the summer to breed – the remaining time they spend underground.

For example, the cicadas in Florida and Mississippi appear every 13 years. The cicadas in Illinois and Iowa only appear every 17 years. But there are no cicadas with 12, 14, 15 or 16 year cycles.

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

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.