- Practice
- About 17 min
- 5 practice questions
Euclid's division lemma and Euclid's division algorithm
State Euclid's division lemma for positive and for any integers, use it to prove forms such as 3m or 3m + 1, and find the HCF of two or three numbers with Euclid's division algorithm.
If something looks wrong, please tell us.
By the end of this lesson you can
- Write a = bq + r with 0 ≤ r < |b| and find q and r, including for negative integers.
- Use the lemma to show that every integer, or every square, has a certain form.
- Find the HCF of two or three numbers by Euclid's division algorithm and solve 'greatest number that divides' problems.
Chapter 2 of the Tamil Nadu textbook starts with one of the oldest results in mathematics, from Euclid's Elements. It is really the long division you already know, written as an equation. Repeating it gives a fast way to find the highest common factor of large numbers without factorising them.
Euclid's division lemma
A lemma is a small result used to prove bigger ones. Euclid's division lemma: if a and b are positive integers, there exist unique integers q and r such that a = bq + r, 0 ≤ r < b. Here a is the dividend, b the divisor, q the quotient and r the remainder. The remainder is always less than the divisor. If r = 0, then a = bq and b divides a.
For example, packing 47 mangoes in bags of 6: 47 = 6 × 7 + 5, so 7 full bags and 5 mangoes left over.
Generalised form: for any integers a and b with b ≠ 0, there are unique integers q and r with a = bq + r and 0 ≤ r < |b|. The remainder is never negative, even when a or b is negative.
Worked example 1: quotient and remainder with negative numbers
- a = −17, b = 5: the multiple of 5 just below −17 is −20 = 5 × (−4). So −17 = 5 × (−4) + 3, giving q = −4, r = 3 (0 ≤ 3 < 5).
- a = 23, b = −4: 23 = (−4) × (−5) + 3, since (−4)(−5) = 20. So q = −5, r = 3 (0 ≤ 3 < 4).
- a = −20, b = −6: −20 = (−6) × 4 + 4, since (−6)(4) = −24 and −24 + 4 = −20. So q = 4, r = 4 (0 ≤ 4 < 6).
Worked example 2: proving a form
Show that the square of any integer is of the form 3m or 3m + 1. Working: dividing any integer x by 3 leaves remainder 0, 1 or 2, so x = 3k, 3k + 1 or 3k + 2. Then (3k)² = 9k² = 3(3k²); (3k + 1)² = 9k² + 6k + 1 = 3(3k² + 2k) + 1; (3k + 2)² = 9k² + 12k + 4 = 3(3k² + 4k + 1) + 1. In every case the square is 3m or 3m + 1, so a square never leaves remainder 2 on division by 3.
Euclid's division algorithm
An algorithm is a step-by-step procedure (the word comes from the name of the Persian mathematician al-Khwarizmi). The key fact is: if a = bq + r, then every common divisor of a and b is a common divisor of b and r, and the other way round. So HCF(a, b) = HCF(b, r), and we can keep replacing the pair by a smaller pair.
Euclid's division algorithm for HCF(a, b), a > b
- Divide a by b Write a = bq + r, 0 ≤ r < b.
- Is r = 0? If yes, b is the HCF. Stop.
- If not, divide b by r The old divisor becomes the dividend, the remainder becomes the divisor.
- Repeat until the remainder is 0 The last non-zero divisor is the HCF.
Worked example 3: HCF of 1071 and 462
Working: 1071 = 462 × 2 + 147. Remainder 147 ≠ 0, so divide 462 by 147: 462 = 147 × 3 + 21. Remainder 21 ≠ 0, so divide 147 by 21: 147 = 21 × 7 + 0. The remainder is 0, and the divisor at this stage is 21. HCF(1071, 462) = 21. Check: 1071 = 21 × 51 and 462 = 21 × 22.
Worked example 4: writing the HCF as a combination
Find HCF(455, 42) and write it as 42x + 455y. Working: 455 = 42 × 10 + 35; 42 = 35 × 1 + 7; 35 = 7 × 5 + 0, so the HCF is 7. Now work back: 7 = 42 − 35 × 1, and 35 = 455 − 42 × 10. Substitute: 7 = 42 − (455 − 420) = 42 × 11 − 455. So x = 11, y = −1. Check: 462 − 455 = 7.
HCF of three numbers and remainder problems
For three numbers a, b, c, first find d = HCF(a, b), then HCF(d, c). Example: 192, 288, 120. Working: 288 = 192 × 1 + 96 and 192 = 96 × 2 + 0, so HCF(288, 192) = 96. Then 120 = 96 × 1 + 24 and 96 = 24 × 4 + 0, so HCF(96, 120) = 24. HCF(192, 288, 120) = 24. Two numbers whose HCF is 1 are called relatively prime or coprime; for example 15 and 28.
Worked example 5: greatest number leaving given remainders
Find the greatest number that divides 398 and 436 leaving remainders 7 and 11 respectively. Working: the number must divide 398 − 7 = 391 and 436 − 11 = 425 exactly, so we need HCF(391, 425). 425 = 391 × 1 + 34; 391 = 34 × 11 + 17; 34 = 17 × 2 + 0. The number is 17. Check: 398 = 17 × 23 + 7 and 436 = 17 × 25 + 11.
Euclid's division lemma: a = bq + r, 0 ≤ r < |b|. Euclid's division algorithm: HCF(a, b) = HCF(b, r); repeat until r = 0, and the last divisor is the HCF.
Key takeaways: the remainder in a = bq + r is never negative and is less than |b|. Dividing by 2, 3 or 4 and listing the possible remainders proves statements about forms of integers. Euclid's algorithm finds an HCF by repeated division; for three numbers, apply it twice. Subtract the remainders first when a question gives remainders.
Check your understanding
-
1. By Euclid's division lemma, what are q and r when a = −25 and b = 7?
- q = −4, r = 3
- q = −3, r = −4
- q = −3, r = 4
- q = −4, r = −3
Show answer
Answer: A. We need −25 = 7q + r with 0 ≤ r < 7. The multiple of 7 just below −25 is −28 = 7 × (−4), and −28 + 3 = −25. So q = −4 and r = 3. A remainder can never be negative.
-
2. Using Euclid's division algorithm, what is the HCF of 156 and 48?
- 6
- 12
- 24
- 4
Show answer
Answer: B. 156 = 48 × 3 + 12; then 48 = 12 × 4 + 0. The remainder is 0 when the divisor is 12, so HCF = 12.
-
3. What is the greatest number that divides 285 and 1249 leaving remainders 9 and 7 respectively?
- 69
- 46
- 276
- 138
Show answer
Answer: D. It must divide 285 − 9 = 276 and 1249 − 7 = 1242. 1242 = 276 × 4 + 138; 276 = 138 × 2 + 0. So HCF = 138. Check: 285 = 138 × 2 + 9 and 1249 = 138 × 9 + 7.
-
4. A number leaves remainder 29 when divided by 56. What remainder does it leave when divided by 8?
- 3
- 1
- 5
- 7
Show answer
Answer: C. Write the number as 56q + 29. Since 56q = 8(7q) and 29 = 8 × 3 + 5, the number is 8(7q + 3) + 5. So the remainder is 5.
-
5. Which pair of numbers is coprime?
- 21 and 35
- 15 and 28
- 18 and 45
- 26 and 39
Show answer
Answer: B. 15 = 3 × 5 and 28 = 2² × 7 share no prime, so HCF(15, 28) = 1 and they are coprime. The other pairs have HCF 7, 9 and 13.
Sign in to keep track of the lessons you finish.