Log in to Mathigon

Google
Create New Account

Reset Password     

Share

Send us feedback!

Please let us know if you have any feedback and suggestions, or if you find any errors and bugs in our content.

Sorry, your message couldn’t be submitted. Please try again!

Thanks for your feedback!

Reset Progress

Are you sure that you want to reset your progress, response and chat data for all sections in this course? This action cannot be undone.

Glossary

Select one of the keywords on the left…

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?

START 40 80 120 60 120

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 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 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 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 , because they don’t have any common prime factors which would get “canceled”.