Real Numbers

Euclid Division Alogrith

Euclid’s division algorithm is a way to find the HCF of two numbers by using Euclid’s division lemma. It states that if there are any two integers a and b, there exists q and r such that it satisfies the given condition a = bq + r where 0 ≤ r < b.

The basis of the Euclidean division algorithm is Euclid’s division lemma

Consider two numbers 78 and 980 and we need to find the HCF of these numbers. To do this, we choose the largest integer first, i.e. 980 and then according to Euclid Division Lemma, a = bq + r where 0 ≤ r < b;

980 = 78 × 12 + 44

Now, here a = 980, b = 78, q = 12 and r = 44.

Now consider the divisor 78 and the remainder 44, apply Euclid division lemma again.

78 = 44 × 1 + 34

Similarly, consider the divisor 44 and the remainder 34, apply Euclid division lemma to 44 and 34.

44 = 34 × 1 + 10

Following the same procedure again,

34 = 10 × 3 + 4

10 = 4 × 2 + 2

4 = 2 × 2 + 0

As we see that the remainder has become zero, therefore, proceeding further is not possible. Hence, the HCF is the divisor b left in the last step. We can conclude that the HCF of 980 and 78 is 2.

Let us try another example to find the HCF of two numbers 250 and 75. Here, the larger the integer is 250, therefore, by applying Euclid Division Lemma a = bq + r where 0 ≤ r < b, we have

a = 250 and b = 75

⇒ 250 = 75 × 3 + 25

By applying the Euclid’s Division Algorithm to 75 and 25, we have:

75 = 25 × 3 + 0

As the remainder becomes zero, we cannot proceed further. According to the algorithm, in this case, the divisor is 25. Hence, the HCF of 250 and 75 is 25.

How does Euclid algorithm calculate HCF?

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.

Some Examples Based on Euclid Division algorithm

Q-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.

Q-2 What is the HCF of 225 and 867?

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.

Q-3 What is the HCF of 196 and 38220 ?

38220 is greater than 196.
Applying Euclid’s division algorithm,
38220 = 196 × 195 + 0
Therefore, the HCF of 196 and 38220 is 196

Q-4 What is the HCF of 4052 and 12576?

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

Thank you