PROBLEMS ON EUCLIDS DIVISION ALGORITHM

Problem 1 :

Use Euclid's division algorithm to find HCF of 441, 567, 693.

Solution :

693 > 567 > 441

Finding HCF of 693 and 567 :

693 = 567 x 1 + 126

567 = 126 x 4 + 63

126 = 63 x  2 + 0

HCF of (693 and 567) = 63

  441 = 63 x 7 + 0

While dividing 441 by 63, we get 0 as remainder. So,

HCF of 693, 567 and 441 is 63.

Problem 2 :

Using Euclid's division algorithm, find the largest number that divides 1251, 9377 and 15628 leaving remainders 1, 2 and 3 respectively.

Solution :

1251 - 1 ==> 1250

9377 - 2 ==> 9375

15628 - 3 ==> 15625

15625 > 9375 > 1250

Finding HCF of 15625 and 9375 :

15625 = 9375 x 1 + 6250

9375 = 6250 x 1 + 3125

6250 = 3125 x 2 + 0

LCM of 15625 and 9375 is 3125.

3125 = 1250 x 2 + 625

1250 = 625 x 2 + 0

While dividing 1250 by 625, we get 0 as remainder. So,

HCF of 1250, 9375 and 15625 is 625.

So, the largest number which divides 1251, 9377 and 15628 leaving remainders 1, 2 and 3 respectively is

625

Problem 3 :

Using Euclid's division algorithm find the HCF of 9828 and 14742.

Solution :

14742 > 9828

14742 = 9828 x 1 + 4914

9828 = 4914 x 2 + 0

HCF of (14742 and 9828) is 4914.

Problem 4 :

Using Euclid's division algorithm, find which of the following pairs of numbers are coprime.

(i)  231, 396     (ii)  847, 2160

Solution :

(i) 231, 396

396 > 231

396 = 231 x 1 + 165

231 = 165 x 1 + 66

165 = 66 x 2 + 33

66 = 33 x 2 + 0

HCF of (396, 231) is 33.

(ii) 847, 2160

2160 > 847

2160 = 847 x 2 + 466

847 = 466 x 1 + 381

466 = 381 x 1 + 85

381 = 85 x 4 + 41

85 = 41 x 2 + 3

41 = 3 x 13 + 2

2 = 1 x 2 + 0

HCF of 847 and 2160 is 1. So, these two are coprimes.