8 min readPathway sheetPart I (1 mark) and Part II (2 marks); the HCF of three numbers or an HCF word problem is Part III (5 marks)

Euclid's division lemma, division algorithm and HCF

Euclid's lemma: a = bq + r, 0 ≤ r < b. Keep dividing the divisor by the remainder; the last non-zero remainder is the HCF.

Euclid's division lemmaFor positive integers a > b, there are unique integers q and r with a = bq + r, 0 ≤ r < b

Key stepHCF(a, b) = HCF(b, r)

Coprime numbersTwo numbers whose HCF is 1, e.g. 8 and 15

HCF as a combinationHCF(a, b) = ax + by for some integers x and y

The lemma in plain words

Divide a by b. You get a quotient q and a remainder r. The lemma says a = bq + r, and the remainder is always less than the divisor: 0 ≤ r < b. For given a and b there is only one such pair q, r, so they are unique. Example: 47 = 6 × 7 + 5, with 0 ≤ 5 < 6. For a negative dividend, the remainder must still be 0 or positive: −31 = 6 × (−6) + 5.

Euclid's division algorithm: HCF of a and b (a > b)

1
Apply the lemma: a = bq + r.
2
If r = 0, stop: b is the HCF.
3
If r ≠ 0, apply the lemma to b and r. The divisor becomes the new dividend and the remainder becomes the new divisor.
4★
Repeat until the remainder is 0. The divisor at that step, the last non-zero remainder, is the HCF.
5
For three numbers: HCF(a, b, c) = HCF(HCF(a, b), c).

★ key step

Example 1: HCF of two numbers

Problem

Use Euclid's division algorithm to find the HCF of 1386 and 4914.

Working

Apply the lemma a = bq + r again and again until the remainder is 0.
4914 = 1386 × 3 + 756 (remainder 756 ≠ 0)
1386 = 756 × 1 + 630 (remainder 630 ≠ 0)
756 = 630 × 1 + 126 (remainder 126 ≠ 0)
630 = 126 × 5 + 0 (remainder 0, so stop)
The last divisor, 126, is the HCF. Check: 1386 = 126 × 11 and 4914 = 126 × 39.

Answer

HCF(1386, 4914) = 126

Example 2: a word problem with three numbers

Problem

Three milk tankers hold 504 litres, 588 litres and 714 litres. Find the largest measuring can that empties each tanker exactly a whole number of times.

Working

We need the largest number that divides 504, 588 and 714 exactly: their HCF.
588 = 504 × 1 + 84
504 = 84 × 6 + 0, so HCF(588, 504) = 84.
714 = 84 × 8 + 42
84 = 42 × 2 + 0, so HCF(714, 84) = 42.
Check: 504 ÷ 42 = 12, 588 ÷ 42 = 14 and 714 ÷ 42 = 17.

Answer

The largest can holds 42 litres.

In real life

A tailor cuts rolls of 84 m and 120 m into the longest equal pieces with no waste: each piece is HCF(84, 120) = 12 m. Packing sweets into equal bundles uses the same idea.

Exam angle

2 marks: “Use Euclid's division lemma to find the quotient and remainder when −45 is divided by 7.” −45 = 7 × (−7) + 4, so q = −7 and r = 4, since 0 ≤ 4 < 7.

2 marks: “The HCF of 26 and 91 is written as 26m − 91. Find m.” 91 = 26 × 3 + 13 and 26 = 13 × 2 + 0, so the HCF is 13. Then 26m − 91 = 13 gives 26m = 104 and m = 4.

5 marks: “Find the HCF of 1188, 1584 and 2178 using Euclid's division algorithm.” 1584 = 1188 × 1 + 396; 1188 = 396 × 3 + 0, so HCF(1584, 1188) = 396. 2178 = 396 × 5 + 198; 396 = 198 × 2 + 0, so the HCF of all three is 198. Check: 1188 = 198 × 6, 1584 = 198 × 8, 2178 = 198 × 11.

Remember it

Divide, shift, repeat: the divisor becomes the dividend and the remainder becomes the divisor, until the remainder is zero.