Question

Find the hcf of 445&84 using Euclid's division lemma

Answer 1

Euclid's division algorithm:

According to this the HCF of any two positive integers a and b, with a>b

a= bq+r, 0 ≤r
_____________________________
a= 445 , b= 84

On applying euclid's division Lemma for 84 & 445

445 = (84x5)+25

Here, remainder= 25≠0
So take new Dividend as 84 & divisior as 25

84 = (25×3)+9


Here, remainder= 9≠0
So take new Dividend as 25 & divisior as 9

25= (9×2)+7


Here, remainder= 7≠0
So take new Dividend as 9 & divisior as 7

9 = (7×1)+2


Here, remainder= 2≠0
So take new Dividend as 7 & divisior as 2

7 = (2x3)+1


Here, remainder= 1≠0
So take new Dividend as 7 & divisior as 1

7 = (7x1)+0

Here, the remainder is 0 & last divisor is 1.

Hence , HCF of 445 & 84 is 1