Question

Using the Euclids Division algorithm find the HCF of 50 and 95

Answer 1

Given :

• 95 and 50

To find :

• HCF using the Euclids Division algorithm =?

Step-by-step explanation:

Clearly, 95 > 50

Applying the Euclid's division lemma to 95 and 50, we get

95 = 50 x 1 + 45

Since the remainder 45 ≠ 0, we apply the Euclid's division lemma to divisor 50 and remainder 45 to get

50 = 45 x 1 + 5

We consider the new divisor 45 and remainder 5 and apply the division lemma to get

45 = 5 x 9 + 0

Now, the remainder at this stage is 0.

So, the divisor at this stage, ie, 5 is the HCF of 95 and 50.

Additional Information ➮

Euclid's Division Algorithm (Lemma)

We know that how to divide a positive integer 'a' by another positive integer 'b' by long division method.

Let us consider a = 217 , b = 5 and make the division of 217 by 5 as under :

Dividend

↓

Divisor → 5)217(43 ← Quotient

20

--------

17

15

-----

2 ←Remainder

Clearly, 217 = 5 x 43 + 2

i, e.,

Dividend = Divisor × Quotient + Remainder

Let us consider some more pairs of integers as given below :

(i). a = 191; b = 2; 191 = 2 x 95 + 1

(ii).a = 321; b = 3; 321 = 3 x 107+0

(iii).a = 205; b = 7; 205 = 7 x 29 + 2

(iv). a = 1047; b = 11; 1047=11 x 95+ 2

From the above, we conclude that for each pair of positive integers, a and b, there exists a pair of whole numbers q and r such that a = b × q + r, 0 ≤ r < b, where6q = quotient and r = remainder.

Formal statement of Euclid's Division Lemma

For any two given positive integers a and b, there exist unique integers q and r such that a = bq + r, 0 ≤ r < b, where a = dividend, b = divisor, q = quotient and r = remainder.

Brainly Extra Knowledge :

• Euclid's division Lemma and algorithm are so closely interlinked that people often called former as the division algorithm also.

• Although euclid's division algorithm is state for only positive integers, it can be extended for all integers except zero, i.e., b ≠ 0.