# Divisibility and PrimesGreatest Common Factors

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 **Greatest Common Divisor** or **gcd** of 18 and 30.

Once again, we can use the

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, 2 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:

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

Once again prime numbers are special: the gcd of two different primes is always