GCSE Maths Practice: factors-and-multiples

Question 8 of 10

Use the Euclidean algorithm or prime powers to find the HCF of three numbers efficiently.

‹ ›

\( \begin{array}{l}\text{Find the greatest common divisor of }48,180,\\ \text{and }360.\end{array} \)

Choose one option:

For three numbers: compute GCD of two, then use that result with the third. Always verify by division.

GCD/HCF with Three Numbers — Higher Tier Focus

The greatest common divisor (GCD), also called the highest common factor (HCF), is the largest positive integer that divides two or more numbers exactly. At GCSE Higher level, problems often involve three numbers or require you to use efficient methods such as the Euclidean algorithm, not just factor lists. Mastering both prime factorisation and the Euclidean algorithm makes you faster and more reliable in exams.

Two Core Methods

  1. Prime factorisation: write each number as a product of primes with powers, identify primes common to all numbers, then multiply the smallest powers of those shared primes.
  2. Euclidean algorithm: for two numbers a and b (a ≥ b), compute remainders repeatedly: a = qb + r; replace (a, b) with (b, r) until r = 0. The last non-zero b is the GCD. For three numbers A, B, C, first compute d = GCD(A, B), then compute GCD(d, C).

Worked Examples (Different Numbers)

Example A (Euclidean method): Find GCD(210, 168, 84).

GCD(210,168): 210 = 1·168 + 42 → GCD = 42
GCD(42,84):  84  = 2·42  + 0  → GCD = 42

Therefore, GCD(210,168,84) = 42.

Example B (Prime factorisation): Find GCD(144, 216, 252).

144 = 2^4 × 3^2
216 = 2^3 × 3^3
252 = 2^2 × 3^2 × 7
Common primes: 2^2 and 3^2 → GCD = 4 × 9 = 36

Why the Euclidean Algorithm Is Powerful

Prime factorisation is clear and visual, but for large or awkward values it can be slow. The Euclidean algorithm avoids full factor trees: it uses division and remainders only, making it ideal for big integers or when you need speed under time pressure. Importantly, it scales well to three or more numbers by iterating pairwise.

Common Mistakes

  • Using highest powers instead of lowest when applying prime factorisation across several numbers.
  • Stopping after finding one shared factor and forgetting to check if a larger common factor exists.
  • Mixing up GCD with LCM (LCM uses the highest powers of all primes that appear).
  • Assuming a number divides another without checking; always verify by division.

Applications

GCDs are essential in simplifying ratios and fractions, scheduling problems, tiling or cutting tasks with maximum equal sizes, and number-theoretic arguments. For instance, if three cable lengths must be cut into the longest equal pieces with no waste, the piece length is their GCD.

Quick FAQ

Q: How do I extend Euclid to three numbers?
A: Compute d = GCD(a, b), then GCD(d, c). The operation is associative.

Q: Can the GCD of three numbers ever be larger than the smallest of them?
A: No. It cannot exceed the smallest number.

Q: What if numbers are all powers of 2?
A: The GCD is 2 raised to the smallest exponent among them.

Study Tip

Practise both methods. Use prime powers when numbers factor nicely; switch to Euclid when numbers are large, unfriendly, or when time is short. For three-number questions, think “pair first, then combine.”