Euclid's Division Lemma and Algorithm for CBSE Class 10 Mathematics

In arithmetic, long division is one of the earliest operations we learn. When we divide an integer by another positive integer, we obtain a quotient and a remainder. Euclid's Division Lemma provides a rigorous mathematical formulation of this familiar division process and serves as the bedrock of elementary number theory in CBSE Class 10 Mathematics.

Beyond simple division, this lemma provides a powerful algorithm for computing the Highest Common Factor (HCF) of large numbers and establishes general proofs regarding the algebraic structure of odd, even, square, and cube integers.

What You Will Learn

• Formal statement and algebraic representation of Euclid's Division Lemma
• The critical condition on the remainder ($0 \le r < b$)
• Step-by-step implementation of Euclid's Division Algorithm to calculate HCF
• Rigorous methods to prove properties and forms of positive integers
• Solved CBSE board examination questions and step-by-step solutions
• Common traps and exam strategies for full marks

1. Statement of Euclid's Division Lemma

A lemma is a proven statement used for proving another statement.

Formal Definition

Given two positive integers $a$ and $b$, there exist unique integers $q$ and $r$ satisfying: $a = bq + r, \quad \text{where } 0 \le r < b$

Here:

• $a$ is called the dividend.
• $b$ is called the divisor.
• $q$ is called the quotient.
• $r$ is called the remainder.

$\text{Dividend} = (\text{Divisor} \times \text{Quotient}) + \text{Remainder}$

Important: <u>The remainder $r$ can be zero, but it must always be strictly less than the divisor $b$. It can never be negative.</u>

Concrete Example

If $a = 27$ and $b = 4$: $27 = 4 \times 6 + 3$ Here, $q = 6$ and $r = 3$. Notice that $0 \le 3 < 4$, which satisfies the lemma conditions perfectly.

2. Euclid's Division Algorithm for Finding HCF

An algorithm is a sequence of well-defined steps which gives a procedure for solving a type of problem. Euclid's Division Algorithm is a technique to compute the Highest Common Factor (HCF) of two given positive integers.

Step-by-Step Procedure

To find the HCF of two positive integers, say $c$ and $d$, with $c > d$:

1. Apply Euclid's Division Lemma: Write $c = dq + r$, where $0 \le r < d$.
2. Check Remainder:
   • If $r = 0$, then $d$ is the $\text{HCF}(c, d)$.
   • If $r \ne 0$, apply the division lemma to divisor $d$ and remainder $r$.
3. Continue the Process: Repeat the steps until the remainder becomes $0$. The divisor at this final stage is the required $\text{HCF}(c, d)$.

Solved Example 1: Calculating HCF

Problem: Use Euclid's Division Algorithm to find the HCF of $4052$ and $12576$.

Solution:

• Step 1: Since $12576 > 4052$, apply the lemma: $12576 = 4052 \times 3 + 420 \quad (r = 420 \ne 0)$
• Step 2: Apply the lemma to divisor $4052$ and remainder $420$: $4052 = 420 \times 9 + 272 \quad (r = 272 \ne 0)$
• Step 3: Apply the lemma to $420$ and $272$: $420 = 272 \times 1 + 148 \quad (r = 148 \ne 0)$
• Step 4: Apply the lemma to $272$ and $148$: $272 = 148 \times 1 + 124 \quad (r = 124 \ne 0)$
• Step 5: Apply the lemma to $148$ and $124$: $148 = 124 \times 1 + 24 \quad (r = 24 \ne 0)$
• Step 6: Apply the lemma to $124$ and $24$: $124 = 24 \times 5 + 4 \quad (r = 4 \ne 0)$
• Step 7: Apply the lemma to $24$ and $4$: $24 = 4 \times 6 + 0 \quad (r = 0)$

Since the remainder is now $0$, the divisor at this final stage is $4$. $\text{HCF}(12576, 4052) = 4$

Exam Tip: In board exams, write each division step clearly on a new line showing the division equation $a = bq + r$ alongside the remainder check $r \ne 0$. This guarantees full step marks.

3. Algebraic Applications: Proving Forms of Positive Integers

Euclid's Division Lemma is frequently used to prove general properties about numbers.

Solved Example 2: Proving Odd Integer Forms

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

Solution:

1. Let $a$ be any positive odd integer.
2. Taking $b = 4$, by Euclid's Division Lemma: $a = 4q + r, \quad \text{where } 0 \le r < 4$
3. The possible values of remainder $r$ are $0, 1, 2,$ and $3$.
4. Thus, $a$ can take four possible forms:
   • When $r = 0$: $a = 4q = 2(2q)$, which is divisible by 2 and therefore even.
   • When $r = 1$: $a = 4q + 1 = 2(2q) + 1$, which is odd.
   • When $r = 2$: $a = 4q + 2 = 2(2q + 1)$, which is divisible by 2 and therefore even.
   • When $r = 3$: $a = 4q + 3 = 2(2q + 1) + 1$, which is odd.
5. Since $a$ is given to be an odd integer, $a$ cannot be $4q$ or $4q + 2$.
6. Therefore, <u>any positive odd integer is of the form $4q + 1$ or $4q + 3$</u>.

Solved Example 3: Form of Squares of Integers

Problem: Use Euclid's Division Lemma to show that the square of any positive integer is either of the form $3m$ or $3m + 1$ for some integer $m$.

Solution:

1. Let $a$ be any positive integer. Taking divisor $b = 3$, by Euclid's Division Lemma: $a = 3q + r, \quad \text{where } r = 0, 1, 2$ So, $a = 3q$, $a = 3q + 1$, or $a = 3q + 2$.
2. Case I ($a = 3q$): $a^2 = (3q)^2 = 9q^2 = 3(3q^2) = 3m \quad (\text{where } m = 3q^2)$
3. Case II ($a = 3q + 1$): $a^2 = (3q + 1)^2 = 9q^2 + 6q + 1 = 3(3q^2 + 2q) + 1 = 3m + 1 \quad (\text{where } m = 3q^2 + 2q)$
4. Case III ($a = 3q + 2$): $a^2 = (3q + 2)^2 = 9q^2 + 12q + 4 = 9q^2 + 12q + 3 + 1 = 3(3q^2 + 4q + 1) + 1 = 3m + 1 \quad (\text{where } m = 3q^2 + 4q + 1)$
5. Hence, the square of any positive integer is always of the form $3m$ or $3m + 1$.

4. Summary and Key Takeaways

Remember: A lemma is an intermediate theorem used to prove other results, while an algorithm is an iterative computational method.

Common Mistake: Writing the inequality as $0 < r < b$ instead of $0 \le r < b$. Always remember that the remainder can equal zero!