Ever tried sharing a pizza among friends and wondered why some slices are left over? That leftover bit is the idea behind Euclid's division lemma – a handy rule for any whole numbers.
💡 In Simple Words: When you divide any number a by a positive number b, you will always get a quotient (the whole‑number result) and a remainder (what's left). The lemma says you can write this asa = b·q + rwhere0 ≤ r . No matter what numbers you pick, such aqandralways exist and are unique.
What is Euclid's Division Lemma?
Euclid's division lemma (also called the division algorithm) is a basic fact about integers. It tells us that for any two integers a and b (with b > 0), you can find exactly one pair of integers q (quotient) and r (remainder) that satisfy:
a = b·q + r and 0 ≤ r .
Think of b as the size of a bucket and a as a pile of water. You pour water into full buckets until you can’t fill another one. The number of full buckets is q, and the water left over is r. The leftover can never be as much as a whole bucket, which is why r is always smaller than b.
Why does it matter in the Real Numbers chapter?
CBSE’s Real Numbers chapter uses this lemma to prove that every integer can be broken down into prime factors (the Fundamental Theorem of Arithmetic). It also helps when you work with greatest common divisors (GCD) and least common multiples (LCM). In short, the lemma is the “starter engine” for many later proofs.
Worked Example 1: Positive numbers
Find q and r when a = 27 and b = 5.
- Divide 27 by 5. 5 goes into 27 five times (5 × 5 = 25).
- Remainder = 27 − 25 = 2.
So, q = 5 and r = 2. Check:
27 = 5·5 + 2 and 0 ≤ 2 . Works perfectly!
Worked Example 2: Including a negative dividend
Find q and r for a = -14 and b = 4.
- We need a remainder that is non‑negative and less than 4.
- Try
q = -4:4·(-4) = -16. Thenr = a - b·q = -14 - (-16) = 2.
Now r = 2 satisfies 0 ≤ 2 . Hence -14 = 4·(-4) + 2. The pair (q, r) = (-4, 2) is unique.
Key Points Summary
| Concept | What to Remember |
|---|---|
| Quotient (q) | The whole‑number part of the division. |
| Remainder (r) | What’s left; always 0 ≤ r |
| Uniqueness | Only one pair (q, r) works for given a and b. |
| Why it works | Think of filling buckets – you can’t have two different ways to fill the same amount. |
📝 Likely Exam Questions
- Q1. State Euclid's division lemma in your own words.
Answer: For any integers a and b (b > 0) there exist unique integers q and r such that a = bq + r and 0 ≤ r - Q2. Find the quotient and remainder when 83 is divided by 9.
Answer: 9 goes into 83 nine times (9 × 9 = 81). Remainder = 83 − 81 = 2. So q = 9, r = 2. - Q3. Explain why the remainder must be less than the divisor.
Answer: If the remainder were equal to or larger than the divisor, you could take one more whole divisor out, increasing the quotient and reducing the remainder – contradicting the definition of remainder. - Q4. Use Euclid's division lemma to express -23 as 5q + r (0 ≤ r Answer: Choose q = -5: 5·(-5) = -25, then r = -23 - (-25) = 2. Hence -23 = 5·(-5) + 2.
- Q5. How does Euclid's division lemma help in finding the GCD of two numbers?
Answer: The lemma lets us replace a larger number by its remainder when divided by the smaller one. Repeating this step (the Euclidean algorithm) eventually yields the greatest common divisor.