Question

Use Euclid's Division Algorithm to find the HCF of- a) 405 and 2520, b) 960 and 1575.

Answer 1

Hi ,

Euclid's division lemma:

Let a and b any two positive integers . Then there exist two

unique q and r such that

a = bq + r ,

0 less or equal to ' r ' less than b.


a ) 405 and 2520 , start with the larger integer that is , 2520

Apply the division lemma to 2520 and 405 ,

2520 = 405 × 6 + 90

Since the remainder 90 , we apply the division lemma to

405 and 90

405 = 90 × 4 + 45

90 = 45 × 2 + 0

The remainder has now become zero, so procedure stops.

Therefore ,

HCF( 405 , 2520 ) = 45.

b) To find HCF of 960 and 1575

1575 = 960 × 1 + 615

960 = 615 × 1 + 345

615 = 345 × 1 + 270

345 = 270 × 1 + 75

270 = 75 × 3 + 45

75 = 45 × 1 + 30

45 = 30 × 1 + 15

30 = 15 × 2 + 0

Now remainder is equal to zero.

Therefore ,

HCF ( 960 , 1575 ) = 15

I hope this will useful to you.

*****

Answer 2

Euclid division lemma:-
a=bq+r
0≤r
(a)405 and 2520

2520 = 405 × 6 + 90

405 = 90 × 4 + 45

90 = 45 × 2 + 0

As the remainder is 0,the HCF of 405 and 2520 is 45

HCF (405,2520) = 45

(b)960 and 1575

1575 = 960 × 1 + 615

960 = 615 × 1 + 345

615 = 345 × 1 + 270

345 = 270 × 1 + 75

270 = 75 × 3 + 45

75 = 45 × 1 + 30

45 = 30 × 1 + 15

30 = 15 × 2 + 0

As the remainder is 0,HCF of 960 and 1575 is 15.

HCF (960,1575) = 15

★hope it helps★