Euclid's Division Lemma and Division Algorithm

Euclid's Division Lemma — The Idea Behind Division

You have been dividing numbers since primary school. When you divide 17 by 5, you say the quotient is 3 and the remainder is 2. Euclid simply wrote this familiar fact as a precise statement.

Euclid's Division Lemma: Given two positive integers $a$ and $b$, there exist unique whole numbers $q$ and $r$ such that $$a = bq + r, \quad 0 \le r < b$$

Here $a$ is the dividend, $b$ is the divisor, $q$ is the quotient, and $r$ is the remainder.

The key condition is $0 \le r < b$ — the remainder is never negative and is always smaller than the divisor. For our $17 = 5 \times 3 + 2$ example: $a=17$, $b=5$, $q=3$, $r=2$, and indeed $0 \le 2 < 5$.

Key Point: The word 'lemma' simply means a small proven statement that we use as a stepping stone to prove bigger results. 'Unique' means there is only one possible pair $(q, r)$ for each $a$ and $b$.

[Board Important] A common mistake is to write a remainder equal to or larger than the divisor. Always reduce until $0 \le r < b$.

Euclid's Division Algorithm — Finding the HCF

The real power of the lemma is that it gives us a reliable, repeatable method to find the HCF (Highest Common Factor, also called GCD) of two positive integers. This step-by-step procedure is Euclid's Division Algorithm.

The Steps

To find the HCF of two positive integers $a$ and $b$ (with $a > b$):

1. Apply the division lemma: write $a = bq + r$.
2. If $r = 0$, then the HCF is $b$ — stop.
3. If $r \neq 0$, apply the lemma again to $b$ and $r$ (the old divisor becomes the new dividend, the remainder becomes the new divisor).
4. Repeat until the remainder becomes 0. The divisor at that final stage is the HCF.

Why it works: At every step, the common factors of the two numbers stay exactly the same. So the last non-zero remainder shares all the common factors of the original pair — it is their HCF.

Worked Outline — HCF of 455 and 42

• $455 = 42 \times 10 + 35$
• $42 = 35 \times 1 + 7$
• $35 = 7 \times 5 + 0$ ← remainder 0

The last divisor is $7$, so $\text{HCF}(455, 42) = 7$.

[Board Important] Show every line of the algorithm in the exam. Marks are awarded for each correct division step, not just the final answer.

Properties of Positive Integers Using the Lemma

Euclid's lemma is also a neat tool to prove general statements about the form of integers. The trick is to take the divisor $b$ as a fixed small number and list the possible remainders.

Every integer is of a fixed form

Take $b = 2$. By the lemma, any integer $a$ can be written as $a = 2q + r$ where $r = 0$ or $r = 1$. So every integer is either even ($2q$) or odd ($2q+1$) — there is no third option.

Similarly, taking $b = 3$, every integer is of the form $3q$, $3q+1$, or $3q+2$.

A classic result

Claim: Every positive odd integer is of the form $4q + 1$ or $4q + 3$.

Reasoning: Take $b = 4$. Any integer is $4q$, $4q+1$, $4q+2$, or $4q+3$. The forms $4q$ and $4q+2$ are even. So an odd integer must be $4q+1$ or $4q+3$.

Exam Tip: These 'form of an integer' proofs are favourite long-answer questions. The method is always the same: pick the right divisor $b$, list the remainder cases, and eliminate the ones that don't fit.

A Note for CBSE vs State Board Students

If you are following the latest rationalised CBSE syllabus, Euclid's Division Lemma has been moved out of the prescribed Class 10 textbook — CBSE now finds HCF and LCM mainly through prime factorisation (covered in the next section).

However, many State Boards still include Euclid's Division Algorithm, and it remains an elegant, exam-friendly method. It is also genuinely useful and builds strong number-sense.

Key Point: Whether or not it is in your exact syllabus, learning this method costs little and pays off — it deepens your understanding of division and the HCF. CBSE students can treat it as enrichment; State Board students should master it as core content.

[Board Important] Know both methods for HCF — Euclid's algorithm (this section) and prime factorisation (next section). Examiners may ask for a specific one.

Solved Examples

Example 1: Apply the division lemma

For $a = 91$ and $b = 8$, find $q$ and $r$ in $a = bq + r$.

Solution:

1. Divide 91 by 8: $8 \times 11 = 88$, leaving $91 - 88 = 3$.
2. So $q = 11$, $r = 3$.
3. Check the condition: $0 \le 3 < 8$. ✓

Final Answer: $91 = 8 \times 11 + 3$.

Takeaway: Always verify $0 \le r < b$ — it confirms you've fully divided.

Example 2: HCF by Euclid's algorithm

Find the HCF of 135 and 225 using Euclid's Division Algorithm.

Solution:

1. Here $225 > 135$, so $225 = 135 \times 1 + 90$.
2. Now apply to 135 and 90: $135 = 90 \times 1 + 45$.
3. Now apply to 90 and 45: $90 = 45 \times 2 + 0$.
4. Remainder is 0; the last divisor is $45$.

Final Answer: $\text{HCF}(135, 225) = 45$.

Takeaway: Each step uses the previous divisor and remainder as the new pair.

Example 3: HCF of 196 and 38220

Find the HCF of 196 and 38220.

Solution:

1. $38220 = 196 \times 195 + 0$ (since $196 \times 195 = 38220$).
2. The remainder is 0 in the very first step, so the divisor 196 is the HCF.

Final Answer: $\text{HCF}(196, 38220) = 196$.

Takeaway: If the smaller number divides the larger exactly, it is itself the HCF.

Example 4: HCF of 867 and 255

Use Euclid's algorithm to find $\text{HCF}(867, 255)$.

Solution:

1. $867 = 255 \times 3 + 102$.
2. $255 = 102 \times 2 + 51$.
3. $102 = 51 \times 2 + 0$.
4. Last divisor = 51.

Final Answer: $\text{HCF}(867, 255) = 51$.

Takeaway: Keep going until the remainder is exactly 0 — never stop early.

Example 5: Largest number dividing with given remainders

Find the largest number that divides 245 and 1029, leaving remainder 5 in each case.

Solution:

1. If the remainder is 5, then the number divides $245 - 5 = 240$ and $1029 - 5 = 1024$ exactly.
2. So the required number is $\text{HCF}(240, 1024)$.
3. $1024 = 240 \times 4 + 64$; $240 = 64 \times 3 + 48$; $64 = 48 \times 1 + 16$; $48 = 16 \times 3 + 0$.
4. HCF $= 16$.

Final Answer: The largest such number is $16$.

Takeaway: 'Leaves remainder r' means subtract r first, then take the HCF of the reduced numbers.

Example 6: Form of an integer

Show that any positive odd integer is of the form $6q + 1$, $6q + 3$, or $6q + 5$, where $q$ is some integer.

Solution:

1. By the division lemma with $b = 6$, any integer $a$ is one of $6q, 6q+1, 6q+2, 6q+3, 6q+4, 6q+5$.
2. The forms $6q$, $6q+2$, $6q+4$ are all even (each is a multiple of 2).
3. So an odd integer must take one of the remaining forms: $6q+1$, $6q+3$, or $6q+5$.

Final Answer: Every positive odd integer is $6q+1$, $6q+3$, or $6q+5$.

Takeaway: List all remainder cases, then strike out the ones that contradict the condition (here, evenness).

Example 7: Maximum columns for a parade

An army contingent of 616 members is to march behind an army band of 32 members. 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:

1. The maximum number of columns common to both groups is $\text{HCF}(616, 32)$.
2. $616 = 32 \times 19 + 8$.
3. $32 = 8 \times 4 + 0$.
4. Last divisor = 8.

Final Answer: They can march in a maximum of $8$ columns.

Takeaway: 'Maximum equal groups from two quantities' is always an HCF problem.

Example 8: HCF used to simplify a fraction

Reduce the fraction $\dfrac{1023}{1219}$ to its lowest terms.

Solution:

1. Find $\text{HCF}(1219, 1023)$: $1219 = 1023 \times 1 + 196$.
2. $1023 = 196 \times 5 + 43$.
3. $196 = 43 \times 4 + 24$; $43 = 24 \times 1 + 19$; $24 = 19 \times 1 + 5$; $19 = 5 \times 3 + 4$; $5 = 4 \times 1 + 1$; $4 = 1 \times 4 + 0$.
4. HCF $= 1$, so the fraction is already in lowest terms.

Final Answer: $\dfrac{1023}{1219}$ is already in lowest terms (the numbers are co-prime).

Takeaway: Two numbers with HCF 1 are co-prime; their fraction cannot be reduced further.

Example 9: Largest tape to measure two lengths

Find the length of the longest measuring tape that can measure the dimensions 825 cm and 675 cm an exact number of times.

Solution:

1. The longest such tape length is $\text{HCF}(825, 675)$.
2. $825 = 675 \times 1 + 150$.
3. $675 = 150 \times 4 + 75$.
4. $150 = 75 \times 2 + 0$. HCF $= 75$.

Final Answer: The longest tape is $75$ cm.

Takeaway: 'Longest length that measures both exactly' = HCF of the two lengths.

Example 10: Square of an odd integer

Using the division lemma, show that the square of any positive odd integer is of the form $8m + 1$ for some integer $m$.

Solution:

1. Any odd integer can be written as $a = 4q + 1$ or $a = 4q + 3$ (from $b = 4$, odd cases).
2. Case 1: $a = 4q+1 \Rightarrow a^2 = 16q^2 + 8q + 1 = 8(2q^2 + q) + 1 = 8m + 1$.
3. Case 2: $a = 4q+3 \Rightarrow a^2 = 16q^2 + 24q + 9 = 8(2q^2 + 3q + 1) + 1 = 8m + 1$.
4. In both cases $a^2 = 8m + 1$.

Final Answer: The square of any positive odd integer is of the form $8m + 1$.

Takeaway: Split into the possible odd forms, square each, and factor out the common multiple to reveal the required pattern.