???
Well done!
Archie

## Glossary

Select one of the keywords on the left…

# Divisibility and PrimesLowest Common Multiples

Reveal All Steps

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

 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 prime factorisation of both:

 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:

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:

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

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

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