# Divisibility and PrimesLeast 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 **least 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