Ever wondered why any two numbers can be expressed as a multiple plus a tiny leftover?
Euclid’s Division Lemma says that when you divide a whole number by another, you’ll always get a quotient (how many times it fits) and a remainder (what’s left over), and the remainder is smaller than the divisor.
What is Euclid’s Division Lemma?
In plain words the lemma guarantees that for any two positive integers a (the larger number) and b (the smaller number) you can write
a = b·q + r
Here q is the quotient – think of it as the number of full “packs” of b that fit inside a. r is the remainder – the bits that don’t make a full pack. The key rule is 0 ≤ r , meaning the remainder is never negative and is always smaller than the divisor.
Why does it matter in Real Numbers?
The lemma is the backbone of many CBSE Class 10 problems: finding greatest common divisors (GCD), simplifying fractions, and proving that certain numbers are prime. Without this simple “pack‑and‑leftover” idea, we couldn’t break down numbers systematically.
Formal statement (in kid‑friendly language)
For any two natural numbers a and b (with b ≠ 0), there exist unique integers q and r such that a = bq + r and 0 ≤ r . “Unique” means there’s only one correct pair of q and r for a given a and b.
Worked Example 1: Simple division
Find the quotient and remainder when 27 is divided by 5.
- How many full 5’s fit into 27? 5×5 = 25, 5×6 = 30 (too big). So q = 5.
- What’s left after taking away 5×5 = 25 from 27? r = 27 – 25 = 2.
Check: 27 = 5·5 + 2, and 0 ≤ 2
Worked Example 2: Using the lemma to find GCD
Find the GCD of 48 and 18 using Euclid’s algorithm (which repeatedly applies the division lemma).
- 48 ÷ 18 → quotient 2, remainder 12. So 48 = 18·2 + 12.
- Now divide the previous divisor (18) by the remainder (12): 18 = 12·1 + 6.
- Next, 12 = 6·2 + 0. When the remainder becomes 0, the last non‑zero remainder (here 6) is the GCD.
Thus, GCD(48,18) = 6.
Quick Summary – Key Points at a Glance
| Term | Meaning (in everyday words) |
|---|---|
| Divisor (b) | The number you are dividing into another. |
| Quotient (q) | How many whole times the divisor fits. |
| Remainder (r) | What’s left after taking out all whole packs. |
| Uniqueness | Only one pair (q,r) works for a given a and b. |
How Euclid’s Lemma Connects to Other Topics
Once you master the lemma, you’ll see it pop up in:
- Prime factorisation – breaking a number down into prime “building blocks”.
- Finding least common multiples (LCM) – the smallest number that both numbers fit into without leftovers.
- Proofs about divisibility – showing that if a number divides a product, it must divide at least one factor.
📝 Likely Exam Questions
- State Euclid’s Division Lemma and explain each part.
Answer: For any integers a and b (b≠0) there exist unique integers q and r such that a = bq + r and 0 ≤ r - Find the quotient and remainder when 123 is divided by 11.
Answer: 11×11 = 121, remainder 2. So q = 11, r = 2. - Use Euclid’s Division Lemma to compute GCD(84,30).
Answer: 84 = 30·2 + 24; 30 = 24·1 + 6; 24 = 6·4 + 0 → GCD = 6. - Explain why the remainder must be less than the divisor.
Answer: If the remainder were equal to or larger than the divisor, we could increase the quotient by one and reduce the remainder, contradicting the definition of “full packs”. - Show that 17 is a prime number using the division lemma.
Answer: Test divisors 2‑4 (since √17≈4). 17 = 2·8 + 1, 17 = 3·5 + 2, 17 = 4·4 + 1. All remainders are non‑zero, so no divisor other than 1 and 17 divides 17; thus 17 is prime.