Question

USE EUCLID'S DIVISION ALGORITHM TO FIND HCF :-

(i) 196 AND 38220 (ii)867 and 255

Answer 1

Answer:

Mark as BRAINLEST

Step-by-step explanation:

We will be finding the HCF of given integers by using Euclid’s Division Lemma. It is a technique to compute the highest common factor of two given positive integers.

To obtain the HCF of two positive integers say a and b with a > b, follow the steps described below:

Step I: Apply Euclid’s division lemma to a and b. So, we find whole numbers q and r such that: a = bq + r, 0 ≤ r < b

NOTE: Here, a = dividend, b = divisor, q = quotient, r = remainder.

Step II: If r = 0, b is the HCF of a and b. If r ≠ 0, apply Euclid's division lemma to b and r.

Step III: Continue the process until the remainder is zero. The divisor at this stage will be the required HCF.

(i) 135 and 225

In this case, 225 > 135. We apply Euclid’s division lemma to 135 and 225 and get 225 = (135 × 1) + 90

Since, the remainder r ≠ 0, we apply the division lemma to 135 and 90 to get 135 = (90 × 1) + 45

Since, the remainder r ≠ 0, now, we consider 90 as the divisor and 45 as the remainder and apply division lemma, to get 90 = (45 × 2) + 0

Since the remainder is zero and the divisor is 45, therefore, the HCF of 135 and 225 is 45.

(ii) 196 and 38220

38220 is greater than 196. We apply Euclid’s division lemma to 38220 and 196, to get 38220 = (196 × 195) + 0

Since the remainder is zero and the divisor in this step is 195, therefore, the HCF of 38220 and 196 is 196.

(iii) 867 and 255

867 is greater than 225 and on applying Euclid’s division lemma to 867and 225, we get 867 = (255 × 3) + 102

Since the remainder r ≠ 0, we apply the division lemma to 225 and 102 to get 255 = (102 × 2) + 51

Again, the remainder is not zero, we apply Euclid’s division lemma to 102 and 51 which gives us 102 = (51 × 2) + 0

Since the remainder is zero and the divisor is 51, therefore, the HCF of 867 and 255 is 51.

Answer 2

Answer:

(i) 135 and 225

Step 1:

Here, 225 is greater than 135.

Euclid’s division lemma: a = bq + r, (0 ≤ r < b)

Apply Euclid’s division lemma to a = 225 and b = 135 to find r and q such that

225 = 135q + r, (0 ≤ r < 135)

Here, We Dividing 225 by 135 we will get 1 as the quotient and 90 as remainder.

i.e. 225 = (135 × 1) + 90

Step 2:

Here, Remainder r is 90 and it is not equal to 0, we apply Euclid’s division lemma to 135 and

90 to find whole numbers q and r such that

135 = 90 × q + r, ( 0 ≤ r < 90);

Here, dividing 135 by 90 we get 1 as the quotient and 45 as remainder.

i.e. 135 = (90 × 1) + 45

Step 3:

Again, the remainder r is 45 and it is not equal to 0, so we apply Euclid’s division lemma to

new divisor 90 and new remainder 45 to find q and r such that

90 = 45 × q + r, 0 ≤ r < 45

Here, dividing 90 by 45 we get 2 as the quotient and 0 as remainder.

i.e. 90 = (2 × 45) + 0

Step 4:

So, the remainder is zero, the divisor at this stage will be HCF of 135, 225.

Here, the divisor at this stage is 45; as a result, the HCF of 135 and 225 is 45.

Hence, the HCF of 135 and 225 is 45.

(ii) 196 and 38220

Step 1:

Here, 38220 is greater than 196.

Euclid’s division lemma: a = bq + r, (0 ≤ r < b)

Apply Euclid’s division lemma to a = 38220 and b = 196 to find whole numbers q and r,

such that ,

38220 = 196 q + r, (0 ≤ r < 196)

Here, dividing 38220 by 196, we will get 195 as the quotient and 0 as remainder

i.e. 38220 = (196 × 195) + 0

Because the remainder is zero, divisor at this stage will be HCF.

Here, divisor at this stage is 196; as a result HCF of 196 and 38220 is 196.

Hence, the HCF of 196 and 38220 is 196.

(iii) 867 and 255

Step 1:

Here, 867 is greater than 255.

Euclid’s division lemma: a = bq + r, (0 ≤ r < b)

Apply Euclid’s division lemma to a = 867 and b = 255 to find q and r, such that:

867 = 255q + r, (0 ≤ r < 255)

So, dividing 867 by 255 we will get 3 as the quotient and 102 as remainder.

So 867 = 255 × 3 + 102

Step 2:

Here, remainder is 102 and it is not equal to 0, we may apply the division lemma to new a =

255 and b= 102 to find whole numbers q and r, such that:

255 = 102q + r, (0 ≤ r < 102)

So, dividing 255 by 102 we get 2 as the quotient and 51 as remainder.

So, 255 = 102 × 2 + 51

Step 3:

Again, the remainder 51 is not equal to zero, so we apply the division lemma to a = 102 and b

= 51 to find whole numbers q and r such that

102 = 51 q + r, (0 ≤ r < 51)

So, dividing 102 by 51 we get 2 as the quotient and 0 as remainder.

Here, 102 = 51 × 2 + 0.

Here, the value of remainder is zero; the value of divisor at this stage is the HCF. Since the

divisor at this stage is 51. As a result, HCF of 867 and 255 is 51.

Hence, the HCF of 867 and 255 is 51