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
Once again, we can use the
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
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