???
Well done!
Archie

## 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?

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 Factor or gcf of 18 and 30.

Once again, we can use the prime factorisation to calculate the gcf of any two numbers. Remember that any factor 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 gcf 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 bothone of 18 and 30:

X  =  2 × 3  =  6.

Now we have a simple method for finding the gcf 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 gcf of two different primes is always , because they don’t share any prime factors.