Euclid's Division Lemma
Euclid's Division Lemma is a fundamental result in number theory that formalises the process of long division.
Named after the Greek mathematician Euclid, who described it in Elements (300 BCE), this lemma is the mathematical backbone of the division algorithm.
In CBSE Class 10 Mathematics (Chapter 1: Real Numbers), Euclid's Division Lemma serves as the foundation for Euclid's Division Algorithm — a systematic method to compute the HCF of two positive integers.
Key uses of this lemma:
- Solving HCF problems efficiently
- Proving divisibility results
- Expressing integers in specific forms (e.g., 3q, 3q + 1, 3q + 2)
What is Euclid's Division Lemma?
Definition: Given any two positive integers a and b, there exist unique integers q (quotient) and r (remainder) such that:
a = bq + r, where 0 ≤ r < b
Where:
- a = dividend
- b = divisor
- q = quotient
- r = remainder
The lemma guarantees two things:
- Existence: Such integers q and r always exist for any positive integers a and b.
- Uniqueness: There is exactly one pair (q, r) satisfying the equation with 0 ≤ r < b.
The condition 0 ≤ r < b means:
- The remainder is always non-negative
- The remainder is strictly less than the divisor
- When r = 0, b divides a exactly (a is a multiple of b)
Examples:
- a = 37, b = 7: 37 = 7 × 5 + 2 (q = 5, r = 2, and 0 ≤ 2 < 7)
- a = 42, b = 6: 42 = 6 × 7 + 0 (q = 7, r = 0, meaning 6 divides 42 perfectly)
Important:
- In NCERT Class 10, the lemma is restricted to positive integers.
- b cannot be zero (division by zero is undefined).
- The lemma is the statement (existence + uniqueness). The algorithm is the procedure that uses this lemma repeatedly to find HCF.
Euclid's Division Lemma Formula
Formula:
a = bq + r, where 0 ≤ r < b
Related results:
- If r = 0: a = bq, meaning b divides a exactly. Written as b | a.
- Remainder formula: r = a − bq, or equivalently r = a mod b.
- Connection to HCF: HCF(a, b) = HCF(b, r). This property makes Euclid's Algorithm work.
- Termination condition: When r = 0, the divisor at that step is the HCF.
- Number of possible remainders: When dividing by b, there are exactly b possible remainders: 0, 1, 2, ..., b − 1.
Forms of integers (useful for proofs):
- Dividing by 2: n = 2q (even) or n = 2q + 1 (odd)
- Dividing by 3: n = 3q, or n = 3q + 1, or n = 3q + 2
- Dividing by 4: n = 4q, or n = 4q + 1, or n = 4q + 2, or n = 4q + 3
Derivation and Proof
Why does Euclid's Division Lemma work?
Step 1 — Number line visualisation:
The multiples of b on the number line are: 0, b, 2b, 3b, 4b, ....
- If a falls exactly on qb, then a = bq + 0 (remainder 0).
- If a falls between qb and (q+1)b, then r = a − qb, and 0 < r < b.
Step 2 — Existence proof:
Let q be the largest integer such that bq ≤ a. Define r = a − bq.
- r ≥ 0 because bq ≤ a.
- r < b because if r ≥ b, then b(q+1) ≤ a, contradicting q being the largest such integer.
Step 3 — Uniqueness proof:
Suppose a = bq₁ + r₁ and a = bq₂ + r₂, where 0 ≤ r₁ < b and 0 ≤ r₂ < b.
- Then b(q₁ − q₂) = r₂ − r₁.
- Since |r₂ − r₁| < b and the left side is a multiple of b, the only possibility is q₁ = q₂ and r₁ = r₂.
Step 4 — Key insight for Euclid's Algorithm:
HCF(a, b) = HCF(b, r) because:
- Any common divisor of a and b also divides r = a − bq.
- Conversely, any common divisor of b and r also divides a = bq + r.
- So the set of common divisors of (a, b) equals the set of common divisors of (b, r).
Step 5 — Application to number theory proofs:
Problem: Show that the square of any positive integer is of the form 3m or 3m + 1.
By Euclid's Lemma, any integer n = 3q, 3q + 1, or 3q + 2.
- If n = 3q: n² = 9q² = 3(3q²) = 3m
- If n = 3q + 1: n² = 9q² + 6q + 1 = 3(3q² + 2q) + 1 = 3m + 1
- If n = 3q + 2: n² = 9q² + 12q + 4 = 3(3q² + 4q + 1) + 1 = 3m + 1
Therefore, n² is always of the form 3m or 3m + 1.
Types and Properties
Forms of integers based on divisor:
| Divisor | Possible Forms | Application |
|---|---|---|
| 2 | 2q (even), 2q + 1 (odd) | Properties of even/odd numbers |
| 3 | 3q, 3q + 1, 3q + 2 | Divisibility by 3, remainders mod 3 |
| 4 | 4q, 4q + 1, 4q + 2, 4q + 3 | Patterns in squares |
| 6 | 6q, 6q + 1, ..., 6q + 5 | All primes > 3 are 6k ± 1 |
Special cases of the lemma:
- When r = 0: b divides a perfectly. Example: 48 = 12 × 4 + 0 means 12 | 48.
- When a < b: q = 0 and r = a. Example: 5 = 13 × 0 + 5.
- When a = b: q = 1 and r = 0. Example: 7 = 7 × 1 + 0.
Common CBSE exam problem types:
- Type A: Find the HCF of two numbers using Euclid's Division Algorithm.
- Type B: Show that every positive integer is of a certain form (e.g., 4q, 4q + 1, 4q + 2, or 4q + 3).
- Type C: Prove properties of squares or cubes (e.g., cube of any positive integer is of the form 9m, 9m + 1, or 9m + 8).
- Type D: Show that the product of consecutive integers is divisible by a given number.
Generalisation:
The Division Lemma extends to polynomials. For polynomials f(x) and g(x) with g(x) ≠ 0, there exist unique polynomials q(x) and r(x) such that f(x) = g(x) × q(x) + r(x), where degree of r(x) < degree of g(x).
Solved Examples
Example 1: Basic application of Euclid's Division Lemma
Problem: Express 573 in the form given by Euclid's Division Lemma when divided by 17.
Solution:
Given:
- a = 573, b = 17
Using a = bq + r:
- 573 ÷ 17: 17 × 33 = 561
- r = 573 − 561 = 12
- 573 = 17 × 33 + 12
Verification: 0 ≤ 12 < 17 ✓ and 17 × 33 + 12 = 573 ✓
Answer: 573 = 17 × 33 + 12, where q = 33 and r = 12.
Example 2: When the dividend is smaller than the divisor
Problem: Apply Euclid's Division Lemma to the pair (11, 29).
Solution:
Given:
- Taking the larger number as dividend: a = 29, b = 11
Using a = bq + r:
- 29 ÷ 11: 11 × 2 = 22
- r = 29 − 22 = 7
- 29 = 11 × 2 + 7
Verification: 0 ≤ 7 < 11 ✓
Alternative: If a = 11, b = 29: 11 = 29 × 0 + 11 (q = 0, r = 11, and 0 ≤ 11 < 29 ✓).
Answer: 29 = 11 × 2 + 7 (standard form with larger number as dividend).
Example 3: Finding HCF using Euclid's Division Algorithm
Problem: Use Euclid's Division Algorithm to find the HCF of 4052 and 12576.
Solution:
Steps:
- 12576 = 4052 × 3 + 420 (r = 420 ≠ 0)
- 4052 = 420 × 9 + 272 (r = 272 ≠ 0)
- 420 = 272 × 1 + 148 (r = 148 ≠ 0)
- 272 = 148 × 1 + 124 (r = 124 ≠ 0)
- 148 = 124 × 1 + 24 (r = 24 ≠ 0)
- 124 = 24 × 5 + 4 (r = 4 ≠ 0)
- 24 = 4 × 6 + 0 (r = 0, stop)
The last non-zero remainder is 4.
Answer: HCF(4052, 12576) = 4.
Example 4: Showing integers take a specific form
Problem: Show that every positive integer is of the form 3q, 3q + 1, or 3q + 2 for some integer q ≥ 0.
Solution:
- Let n be any positive integer. Apply Euclid's Division Lemma with divisor b = 3.
- By the lemma, n = 3q + r, where 0 ≤ r < 3.
- Since r can only be 0, 1, or 2:
- If r = 0: n = 3q
- If r = 1: n = 3q + 1
- If r = 2: n = 3q + 2
These three forms cover all positive integers.
Answer: By Euclid's Division Lemma, every positive integer is of the form 3q, 3q + 1, or 3q + 2. ■
Example 5: Proving a property of squares using the lemma
Problem: Prove that the square of any positive integer is of the form 4m or 4m + 1 for some integer m.
Solution:
By Euclid's Division Lemma with b = 2, any positive integer n is either 2k (even) or 2k + 1 (odd).
Case 1 — n = 2k (even):
- n² = (2k)² = 4k² = 4m, where m = k²
Case 2 — n = 2k + 1 (odd):
- n² = (2k + 1)² = 4k² + 4k + 1 = 4(k² + k) + 1 = 4m + 1, where m = k² + k
In both cases, n² is either 4m or 4m + 1.
Answer: The square of any positive integer is of the form 4m or 4m + 1. ■
Example 6: Product of three consecutive integers is divisible by 6
Problem: Prove that the product of three consecutive positive integers is divisible by 6.
Solution:
Given: Three consecutive integers n, n + 1, n + 2. Product P = n(n + 1)(n + 2).
Divisibility by 2:
Among any two consecutive integers, one is even. So at least one of n, n + 1, n + 2 is even, hence 2 | P.
Divisibility by 3:
By Euclid's Division Lemma, n = 3q, 3q + 1, or 3q + 2.
- If n = 3q: 3 | n, so 3 | P
- If n = 3q + 1: n + 2 = 3q + 3 = 3(q + 1), so 3 | (n + 2), hence 3 | P
- If n = 3q + 2: n + 1 = 3q + 3 = 3(q + 1), so 3 | (n + 1), hence 3 | P
Since 2 | P and 3 | P, and gcd(2, 3) = 1, we have 6 | P.
Answer: The product of three consecutive positive integers is always divisible by 6. ■
Example 7: Proving cubes take a specific form
Problem: Show that the cube of any positive integer is of the form 9m, 9m + 1, or 9m + 8.
Solution:
By Euclid's Division Lemma with b = 3, any integer n = 3q, 3q + 1, or 3q + 2.
Case 1 — n = 3q:
- n³ = 27q³ = 9(3q³) = 9m, where m = 3q³
Case 2 — n = 3q + 1:
- n³ = (3q + 1)³ = 27q³ + 27q² + 9q + 1 = 9(3q³ + 3q² + q) + 1 = 9m + 1
Case 3 — n = 3q + 2:
- n³ = (3q + 2)³ = 27q³ + 54q² + 36q + 8 = 9(3q³ + 6q² + 4q) + 8 = 9m + 8
Answer: The cube of any positive integer is of the form 9m, 9m + 1, or 9m + 8. ■
Example 8: Finding the largest number with given remainder conditions
Problem: Find the largest positive integer that divides 398, 436, and 542 leaving remainders 7, 11, and 15 respectively.
Solution:
Given:
- The required number divides (398 − 7) = 391
- The required number divides (436 − 11) = 425
- The required number divides (542 − 15) = 527
Finding HCF(391, 425, 527):
- HCF(391, 425): 425 = 391 × 1 + 34, then 391 = 34 × 11 + 17, then 34 = 17 × 2 + 0. HCF = 17.
- HCF(17, 527): 527 = 17 × 31 + 0. HCF = 17.
Answer: The largest such number is 17.
Example 9: Word problem involving Euclid's Division Lemma
Problem: An army contingent of 616 members is to march behind an army band of 32 members in a parade. The two groups are to march in the same number of columns. What is the maximum number of columns in which they can march?
Solution:
Given:
- Contingent = 616 members, Band = 32 members
- Maximum columns = HCF(616, 32)
Using Euclid's Algorithm:
- 616 = 32 × 19 + 8
- 32 = 8 × 4 + 0
HCF = 8.
Answer: They can march in a maximum of 8 columns.
Example 10: Proving an odd square leaves remainder 1 when divided by 8
Problem: Prove that the square of any odd positive integer is of the form 8m + 1 for some integer m.
Solution:
- Any odd positive integer n = 2k + 1 (by Euclid's Division Lemma with b = 2).
- n² = (2k + 1)² = 4k² + 4k + 1 = 4k(k + 1) + 1.
- k(k + 1) is the product of two consecutive integers, so one of them is even. Therefore k(k + 1) = 2t for some integer t.
- n² = 4(2t) + 1 = 8t + 1 = 8m + 1, where m = t.
Answer: The square of any odd positive integer is of the form 8m + 1. ■
Real-World Applications
Real-world applications of Euclid's Division Lemma:
- Cryptography (RSA Algorithm): RSA encryption, which secures internet banking and e-commerce, relies on modular arithmetic and the Extended Euclidean Algorithm to compute modular inverses.
- Computer Science: The modulo operator (% in Python, C, Java) implements Euclid's Division Lemma. Hashing algorithms, random number generators, and cyclic data structures all depend on the remainder operation.
- Music Theory: The Euclidean rhythm algorithm distributes musical beats evenly, creating rhythms found in African, Middle Eastern, and Latin American music.
- Calendar Calculations: Determining the day of the week for any date uses modular arithmetic. Leap year calculations use divisibility checks.
- Resource Distribution: Dividing 150 chocolates among 12 students: each gets 12 (quotient) with 6 left over (remainder).
- Error-Correcting Codes: Communication systems use polynomial division (a generalisation of Euclid's Division) to detect and correct errors.
Key Points to Remember
- Euclid's Division Lemma: a = bq + r with 0 ≤ r < b. Both q and r are uniquely determined.
- The lemma is a statement (existence + uniqueness). The algorithm is the procedure using the lemma to find HCF.
- HCF(a, b) = HCF(b, r) where a = bq + r. This is the key idea behind Euclid's Algorithm.
- When r = 0, the divisor b is the HCF. This is the stopping condition.
- Any positive integer divided by b gives exactly b possible remainders: 0, 1, 2, ..., b − 1.
- To show integers take certain forms (like 3q, 3q+1, 3q+2), apply the lemma with the appropriate divisor.
- Euclid's Algorithm always terminates because remainders form a strictly decreasing sequence of non-negative integers.
- The algorithm works even when a < b — the first step gives q = 0, r = a, and roles switch.
- Common exam question types: finding HCF, proving integer forms, proving divisibility of products of consecutive integers.
- This topic carries 2–4 marks in CBSE board exams.
Practice Problems
- Use Euclid's Division Algorithm to find the HCF of 135 and 225.
- Use Euclid's Division Lemma to show that any positive integer is of the form 6q + 1, 6q + 3, or 6q + 5, where q is some integer, if the integer is odd.
- Show that the square of any positive integer cannot be of the form 3m + 2.
- Find the HCF of 196 and 38220 using Euclid's Algorithm.
- Prove that the product of two consecutive positive integers is divisible by 2.
- A sweetseller has 420 kaju barfis and 130 badam barfis. She wants to stack them in such a way that each stack has the same number, and they take up the least area of the tray. What is the maximum number of barfis that can be placed in each stack?
- Show that any positive integer of the form 6q + 1 or 6q + 5 is odd, where q is a non-negative integer.
- Use Euclid's Division Algorithm to find the HCF of 56, 96, and 404.
Frequently Asked Questions
Q1. What is Euclid's Division Lemma in simple words?
Euclid's Division Lemma states that when you divide any positive integer a by another positive integer b, you always get a unique quotient q and remainder r such that a = bq + r, where 0 ≤ r < b. It is the formal mathematical statement behind long division.
Q2. What is the difference between Euclid's Division Lemma and Euclid's Division Algorithm?
The lemma is the mathematical statement guaranteeing the existence and uniqueness of quotient and remainder. The algorithm is the step-by-step procedure that uses this lemma repeatedly to find the HCF of two numbers. The lemma is the foundation; the algorithm is the application.
Q3. How to find HCF using Euclid's Division Algorithm step by step?
Divide the larger number by the smaller to get quotient and remainder. Then divide the smaller number by the remainder. Continue dividing the previous divisor by the new remainder until the remainder becomes 0. The last non-zero remainder is the HCF. For example, HCF(135, 225): 225 = 135 x 1 + 90, then 135 = 90 x 1 + 45, then 90 = 45 x 2 + 0. HCF = 45.
Q4. Why does Euclid's Division Algorithm always terminate?
Each step produces a remainder strictly less than the previous divisor (0 ≤ r < b). The remainders form a decreasing sequence of non-negative integers: r1 > r2 > r3 > ... which must eventually reach 0. A decreasing sequence of non-negative integers cannot continue indefinitely.
Q5. Can Euclid's Division Lemma be applied when a is less than b?
Yes. If a < b, then q = 0 and r = a. For example, a = 7, b = 15: 7 = 15 × 0 + 7. The lemma gives quotient 0 with the dividend itself as the remainder.
Q6. What happens when the remainder is 0 in Euclid's Division Lemma?
When r = 0, the equation becomes a = bq, meaning b divides a exactly. In Euclid's Algorithm for finding HCF, r = 0 is the termination condition and the divisor b at that step is the HCF.
Q7. Is Euclid's Division Lemma only for positive integers?
In the NCERT Class 10 syllabus, the lemma is stated for positive integers only. A more general version exists for all integers (including negative). The constraint remains: 0 ≤ r < |b|.
Q8. How is Euclid's Division Lemma used to prove number properties?
Set the divisor to an appropriate number (like 2, 3, or 4) to express any integer in possible forms. For example, with divisor 3, every integer is 3q, 3q+1, or 3q+2. Then compute the square or cube of each form to prove the required property.
Q9. What are the important questions from Euclid's Division Lemma for board exams?
The most tested questions are: (1) Find HCF using Euclid's Algorithm (2 marks), (2) Show that every positive integer is of a given form (3 marks), (3) Prove properties of squares or cubes using the lemma (3-4 marks), (4) Word problems requiring HCF (3 marks).
Q10. Who was Euclid and when did he discover this lemma?
Euclid was an ancient Greek mathematician (c. 300 BCE) in Alexandria, Egypt, often called the 'Father of Geometry'. He described the Division Lemma and the related algorithm in Book VII of <em>Elements</em>. The algorithm for finding HCF is one of the oldest algorithms still used in modern computer science.
