Why Euclid’s Division Lemma matters for every CBSE 10th grader
Ever wondered why you can always break a big number into a smaller chunk plus a leftover? That’s Euclid’s division lemma at work – the secret sauce behind the greatest‑common‑divisor (GCD) tricks you’ll see in exams.
💡 In Simple Words: When you divide any whole number a by another whole number b (b ≠ 0), you’ll always get a whole‑number result called the quotient (how many times b fits) and a tiny leftover called the remainder. The lemma guarantees that this leftover is smaller than b.
What is Euclid’s Division Lemma?
Formally, the lemma says: for any two positive integers a and b (with b > 0), there exist unique integers q (quotient) and r (remainder) such that
a = b·q + r and 0 ≤ r .
Think of it like a pizza: you have a slices, you want to put b slices on each plate. q tells you how many full plates you can fill, and r is the few slices left over that don’t fill a whole plate.
How to apply the lemma – step by step
1. Identify the larger number (a) and the smaller divisor (b).
2. Divide a by b using ordinary division (ignore the decimal part). The integer part you get is q.
3. Multiply b by q and subtract the product from a. The result is the remainder r.
4. Check that r is less than b. If it isn’t, you made a mistake.
Worked example 1: a = 29, b = 5
Step 1: 29 ÷ 5 = 5 remainder 4 (ignore the .8). So q = 5.
Step 2: 5 × 5 = 25.
Step 3: 29 − 25 = 4, so r = 4.
Check: 0 ≤ 4
Worked example 2: a = 100, b = 12
100 ÷ 12 = 8 (since 8 × 12 = 96).
Remainder = 100 − 96 = 4.
Thus 100 = 12·8 + 4, and 0 ≤ 4
Why the lemma is the backbone of Euclid’s Algorithm
Euclid’s algorithm finds the GCD of two numbers by repeatedly applying the division lemma. Each step shrinks the numbers until the remainder becomes zero; the last non‑zero remainder is the GCD.
Quick comparison table
| Term | Meaning in everyday life | Mathematical symbol |
|---|---|---|
| Dividend | The total amount you start with (like the whole pizza) | a |
| Divisor | The size of each chunk you’re making (slices per plate) | b |
| Quotient | How many full plates you can fill | q |
| Remainder | Leftover slices that don’t fill a plate | r |
Bullet summary – remember these points
- The lemma works for any two positive integers, no matter how big.
- Quotient q is the integer part of the division; ignore any decimal.
- Remainder r is always smaller than the divisor b.
- Both q and r are unique – there’s only one correct pair for a given a and b.
- Applying the lemma repeatedly leads to Euclid’s algorithm for GCD.
📝 Likely Exam Questions
- State Euclid’s division lemma.
Answer: For any integers a > 0 and b > 0, there exist unique integers q and r such that a = bq + r and 0 ≤ r - Find q and r when 73 is divided by 9.
Answer: 73 ÷ 9 = 8 remainder 1, so q = 8, r = 1. - Use Euclid’s division lemma to show that 48 and 18 are not co‑prime.
Answer: 48 = 18·2 + 12 (r = 12). Then 18 = 12·1 + 6 (r = 6). Finally 12 = 6·2 + 0, so GCD = 6 > 1; hence they are not co‑prime. - Explain why the remainder is always less than the divisor.
Answer: If the remainder were equal to or larger than the divisor, we could increase the quotient by 1 and reduce the remainder, contradicting the definition of q as the greatest integer not exceeding a/b. - Apply Euclid’s algorithm to find GCD(84, 30).
Answer: 84 = 30·2 + 24; 30 = 24·1 + 6; 24 = 6·4 + 0 → GCD = 6.