Real Numbers · Lesson 2 of 5
Euclid Division Lemma
“Because standard long division didn't sound smart enough to put on a resume.”
• Understand the meaning of Euclid's Division Lemma. • Identify the dividend, divisor, quotient and remainder. • Express division in the form a = bq + r. • Verify the condition 0 ≤ r < b. • Apply the lemma to solve numerical problems. • Understand how the lemma forms the basis of finding the HCF.
Introduction
Imagine that 17 chocolates have to be distributed equally among 5 students. Each student receives 3 chocolates, and 2 chocolates remain undistributed.
This simple division can be written as 17 = 5 × 3 + 2. Here, 17 is the dividend, 5 is the divisor, 3 is the quotient and 2 is the remainder.
Whenever one positive integer is divided by another positive integer, the result can always be expressed using the divisor, quotient and remainder. Euclid's Division Lemma describes this relationship.
Euclid's Division Lemma
For any two positive integers a and b, there exist unique whole numbers q and r such that a = bq + r, where 0 ≤ r < b.
The word unique means that for a fixed dividend and divisor, there is only one possible quotient and one possible remainder that satisfy these conditions.
| Symbol | Meaning | Description |
|---|---|---|
| a | Dividend | The number being divided |
| b | Divisor | The number by which a is divided |
| q | Quotient | The number of complete groups |
| r | Remainder | The amount left after division |
The remainder may be zero, but it can never be negative, equal to the divisor or greater than the divisor.
Understanding the Lemma
Consider the division of 17 by 5. The largest multiple of 5 that does not exceed 17 is 15.
Problem
Express 17 in the form a = bq + r.
- 1.Divide 17 by 5.
- 2.The quotient is 3 because 5 × 3 = 15.
- 3.The remainder is 17 − 15 = 2.
- 4.Therefore, 17 = 5 × 3 + 2.
- 5.Since 0 ≤ 2 < 5, the remainder condition is satisfied.
Euclid's Division Lemma does not describe a new method of division. It expresses the result of ordinary division in a precise mathematical form.
Worked Examples
Problem
Express 35 in the form a = bq + r when the divisor is 6.
- 1.Divide 35 by 6.
- 2.The largest multiple of 6 not exceeding 35 is 30.
- 3.Since 30 = 6 × 5, the quotient is 5.
- 4.The remainder is 35 − 30 = 5.
- 5.Therefore, 35 = 6 × 5 + 5.
- 6.Since 0 ≤ 5 < 6, the remainder condition is satisfied.
Problem
Express 52 in the form a = bq + r when the divisor is 8.
- 1.Divide 52 by 8.
- 2.The largest multiple of 8 not exceeding 52 is 48.
- 3.Since 48 = 8 × 6, the quotient is 6.
- 4.The remainder is 52 − 48 = 4.
- 5.Therefore, 52 = 8 × 6 + 4.
- 6.Since 0 ≤ 4 < 8, the remainder condition is satisfied.
Problem
Express 48 in the form a = bq + r when the divisor is 8.
- 1.Divide 48 by 8.
- 2.The quotient is 6 because 8 × 6 = 48.
- 3.Nothing remains after division, so the remainder is 0.
- 4.Therefore, 48 = 8 × 6 + 0.
- 5.Since 0 ≤ 0 < 8, the remainder condition is satisfied.
Important Note
In the equation a = bq + r, the divisor b must be a positive integer. The remainder r must always satisfy 0 ≤ r < b.
If the remainder is zero, the divisor divides the dividend exactly. For example, 48 = 8 × 6 + 0, so 8 divides 48 exactly.
Common Mistakes
The expression 17 = 5 × 2 + 7 is mathematically true, but it is not the correct Euclidean division form because the remainder 7 is greater than the divisor 5. The remainder must satisfy r < b.
The expression 17 = 5 × 4 − 3 is also mathematically true, but it does not satisfy Euclid's Division Lemma because the remainder cannot be negative.
Do not interchange the divisor and quotient. In 35 = 6 × 5 + 5, the divisor is 6 and the quotient is 5.
How to Check an Answer
After finding the quotient and remainder, perform two checks. First, verify that bq + r equals the dividend. Second, verify that the remainder satisfies 0 ≤ r < b.
Problem
Check whether 73 = 9 × 8 + 1 correctly represents Euclid's Division Lemma.
- 1.Calculate the right-hand side: 9 × 8 + 1 = 72 + 1 = 73.
- 2.Therefore, the equation gives the correct dividend.
- 3.The remainder is 1 and the divisor is 9.
- 4.Since 0 ≤ 1 < 9, the remainder condition is satisfied.
- 5.Therefore, the expression is correct.
Quiz
What is the remainder when 42 is divided by 5?
Which condition must the remainder always satisfy?
What does q represent in the equation a = bq + r?
Which expression correctly represents the division of 52 by 8?
Practice Problems
- Express 48 in the form a = bq + r when the divisor is 7.
- Express 73 in the form a = bq + r when the divisor is 9.
- Find the quotient and remainder when 91 is divided by 7.
- Express 100 in the form 13q + r.
- Express 125 in the form 11q + r.
- Verify whether 47 = 6 × 7 + 5 satisfies Euclid's Division Lemma.
- Explain why 29 = 4 × 6 + 5 is not the correct Euclidean division form.
- Can the remainder ever be equal to the divisor? Explain your answer.
Key Takeaways
• Euclid's Division Lemma expresses division in the form a = bq + r. • In the equation, a is the dividend, b is the divisor, q is the quotient and r is the remainder. • The remainder must always satisfy 0 ≤ r < b. • The remainder may be zero, but it cannot be negative or equal to or greater than the divisor. • The quotient and remainder are unique for a fixed dividend and divisor. • Euclid's Division Lemma forms the basis of Euclid's Division Algorithm for finding the HCF.