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.

Problem 5 :

Use Euclid's division algorithm to show of any positive integer is either of the form 3m or 3m + 1 for some integer m.

Solution :

Let a be any positive integer, we know any positive integers is in the form 3q, 3q + 1 or 3q + 2

When a = 3q, then

a² = (3q)²

= 9q²

= 3 (3q²)

Let 3q² = m

= 3m

When a = 3q + 1, then 

a² = (3q + 1)²

= (3q)² + 2(3q) (1) + 1²

= 9q² + 6q + 1

= 3(3q² + 2q) + 1

= 3m + 1

When a = 3q + 2, then 

a² = (3q + 2)²

= (3q)² + 2(3q) (2) + 2²

= 9q² + 12q + 4

= 3(3q² + 4q) + 3 + 1

= 3(3q² + 4q + 1) + 1

= 3m + 1

Here a² is of form of 3m or 3m + 1.

Problem 6 :

Use Euclid's division algorithm to show of any positive integer is either of the form 9q, 9q + 1 or 9q + 8 for some integer q.

Solution :

Let x any positive integer then, it is of the form 3q, 3q + 1 or 3q + 2

When x = 3q then 

x³ = (3q)³

= 27q³

= 9(3q³)

= 9m

When x = 3q + 1 then 

x³ = (3q + 1)³

= (3q)³ + 3 (3q)²(1) + 3 (3q) (1)² + 1³

= 27q³ + 27q² + 9q + 1

= 9q(3q² + 3q + 1) + 1

= 9m + 1

When x = 3q + 2 then 

x³ = (3q + 2)³

= (3q)³ + 3 (3q)²(2) + 3 (3q) (2)² + 2³

= 27q³ + 54q² + 36q + 8

= 9q(3q² + 6q + 4) + 8

= 9m + 8

Hence x³ is either of the form 9m, 9m + 1 or 9m + 8.