Log in to Mathigon

Google
Create New Account

Reset Password     

Share

Change Language

EnglishChinese

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 PrimesGreatest Common Factors

Reveal All Steps

An architect is planning the floor for a large courtyard that measures 18m by 30m. She wants it to be covered in quadratic tiles, without any gaps or overlaps along the sides. What is the largest size of squares she can use?

The tiles have a size of ${x}m.

Just like before, this question is not about geometry - it is about divisibility. The length of the sides of the tiles has to divide both 18 and 30, and the largest possible number with that property is . This is called the Greatest Common Divisor or gcd of 18 and 30.

Once again, we can use the prime factorisation to calculate the gcd of any two numbers. Remember that any divisor of a number must have some of the prime factors of that number.

18
=
2
×
3
×
3
30
=
2
×
3
×
5

Suppose that X is the gcd of 18 and 30. Then X divides 18 so the prime factors of X must be among 2, 3 and 3. Also, X divides 30 so the prime factors of X must be among 2, 3 and 5.

To find X, we simply need to multiply all numbers which are prime factors of 18 and 30:

X  =  2 × 3  =  6.

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

  1. Find the prime factorisation of each number.
  2. Multiple the prime factors which are in both numbers.

Once again prime numbers are special: the gcd of two different primes is always , because they don’t share any prime factors.