Euclid’s Division Lemma

In this article, we will learn-

1. Euclid's Division Lemma: An Introduction

2. Euclid's Division Lemma: Formula

3. Algorithm to Calculate HCF

4. Solved Examples

यदि आप इस लेख को हिंदी भाषा में पढ़ना चाहते हैं, तो कृपया यहां क्लिक करें।

1. Euclid’s Division Lemma: An Introduction

Euclid's Division Lemma is a fundamental principle in number theory and forms the basis of the Euclidean algorithm for finding the greatest common divisor (GCD) of two integers.

This lemma is essentially a formal way of expressing the division process, where you divide a by b to get a quotient q and a remainder r, ensuring that the remainder is always less than the divisor b.

2. Euclid’s Division Lemma: Formula

Euclid’s Division Lemma or Euclid division algorithm states that Given positive integers a and b, there exist unique integers q and r satisfying a = bq + r, 0 ≤ r < b.

where,

    a is the dividend,

    b is the divisor,

    q is the quotient, and

    r is the remainder.

3. Algorithm to Calculate HCF

HCF is the largest number which exactly divides two or more positive integers. The basis of the Euclidean division algorithm is Euclid’s division lemma. To calculate the Highest Common Factor (HCF) of two positive integers a and b we use Euclid’s division algorithm.

To obtain the HCF of two positive integers, say c and d, with c > d, follow the steps given below:

• Step 1: Apply Euclid’s division lemma, to c and d. So, we find whole numbers, q and r such that c = dq + r, 0 ≤ r < d.
• Step 2: If r = 0, d is the HCF of c and d. If r ≠ 0, apply the division lemma to d and r.
• Step 3: Continue the above steps till we get the remainder is zero. The divisor at this stage will be the required HCF.

4. Solved Examples:

Example-1. Find the HCF of 81 and 675 using the Euclidean division algorithm.

Solution: 

The larger integer is 675, therefore, by applying the Division Lemma a = bq + r where 0 ≤ r < b, we have

a = 675 and b = 81

⇒ 675 = 81 × 8 + 27

By applying Euclid’s Division Algorithm again we have,

81 = 27 × 3 + 0

We cannot proceed further as the remainder becomes zero. According to the algorithm, in this case, the divisor is 27. Hence, the HCF of 675 and 81 is 27.

Example-2. What is the HCF of 4052 and 12576?

Solution: 

12576 is greater than 4052.

Applying Euclid’s division algorithm,

12576 = 4052 × 3 + 420

4052 = 420 × 9 + 272

272 = 148 × 1 + 124

148 = 124 × 1 + 24

124 = 24 × 5 + 4

24 = 4 × 6 + 0

Therefore, the HCF of 4052 and 12576 is 4.

Example-3. What is the HCF of 225 and 867?

Solution:

867 is greater than 225

Applying Euclid’s division algorithm,

867 = 225 × 3 + 192

225 = 192 × 1 + 33

192 = 33 × 5 + 27

33 = 27 × 1 + 6

27 = 6 × 4 + 3

6 = 3 × 2 + 0

Therefore, HCF(867, 225) = 3.

Example-4. What is the HCF of 196 and 38220?

Solution:

38220 is greater than 196.

Applying Euclid’s division algorithm,

38220 = 196 × 195 + 0

Therefore, the HCF of 196 and 38220 is 196.

यदि आप इस लेख को हिंदी भाषा में पढ़ना चाहते हैं, तो कृपया यहां क्लिक करें।