EXPRESSING THE HCF OF TWO NUMBERS AS LINEAR COMBINATION

Problem 1 :

If d is the HCF of 56 and 72, find x, y satisfying

d = 56x + 72y

Also show that x and y are not unique.

Solution :

HCF of 56 and 72

56 = 16 × 3 + 8

8 = 4 × 2 + 0

HCF of 56 and 72 is 4.

4 = 56x + 72y

56(4) + 72y

224 + 72y

72y = -224

y = -224/72

y = -3

So, x = 4 and y = -3.

So, x and y are not unique.

Problem 2 :

Express the HCF of 468 and 222 as 468x + 222y where x, y are integers in two different ways.

Solution :

HCF of 468 and 222

468 = 222 × 2 + 44

222 = 24 × 9 + 6

24 = 6 × 4 + 0

HCF of 468 and 222 is 6.

6 = 222 - (24 × 9)

Decomposing 24 as combination of 468 and 222.

6 = 222 - {(468 – 222 × 2) × 9}

6 = 222 - {468 × 9 – 222 × 18}

6 = 222 + (222 × 18) - (468 × 9)

6 = 222(1 + 18) – 468 × 9

6 = 222 × 19 – 468 × 9

6 = 468 × (-9) + 222 × 19

x = -9 and y= 19.

Problem 3 :

Express the HCF of 210 and 55 as 210x + 55y where x, y are integers in two different ways.

Solution :

HCF of 210 and 55

210 = 55 × 3 + 45

55 = 45 × 1 + 10

45 = 10 × 4 + 5

10 = 5 × 2 + 0

HCF of 210 and 55 is 5.

Given, 210x + 55y where x, y are integers.

5 = 210(5) + 55y

5 = 1050 + 55y

55y = -1045

y = -1045/55

y = -19

So, the value of x and y is 5 and -19.

Problem 4 :

If the HCF of 408 and 1032 is expressible in the form of 1032m – 408 × 5. Find m.

Solution :

First let us find HCF of 408 and 1032.

1032 > 408

1032 = 408 × 2 + 216

408 = 216 × 1 + 192

216 = 192 × 1 + 24

192 = 24 × 8 + 0

HCF of 408 and 1032 is 24.

To find m :

1032m – 408 × 5 = 24

1032m – 2040 = 24

1032m = 24 + 2040

1032m = 2064

m = 2064/1032

m = 2

So, the value of m is 2.

Problem 5 :

If the HCF of 657and 963 is expressible in the form of 657n + 963 × (-15). Find n.

Solution :

First let us find HCF of 963 and 657.

963 > 657

963 = 657 ×1 + 306

657 = 306 × 2 + 45

306 = 45 × 6 + 36

45 = 36 × 1 + 9

36 = 9 × 4 + 0

HCF of 657 and 963 is 9.

To find n :

657n + 963 × (-15) = 9

657n – 14445 = 9

657n = 9 + 14445

657n = 14454

n = 14454/657

n = 22

So, the value of n is 22.

Problem 6 :

The product of two numbers if 2028 and their highest common factor is 13. The number of such pairs is  is

a) 1     b)  2     c)  3      d)  4

Solution :

Highest common factor of the number is 13, then 13x and 13y be the two numbers.

Product of two numbers = 2028

13x (13y) = 2028

169xy = 2028

xy = 2028/169

= 12

Co-primes with the product are (1, 12) and (3, 4)

When x = 1, 13 x == > 13(1) ==> 13

When y = 12, 13 y == > 13(12) ==> 156

When x = 3, 13 x == > 13(3) ==> 39

When x = 4, 13 x == > 13(4) ==> 52

2 pairs is the answer.

Problem 7 :

The greatest number which can divide 1356, 1868 and 2764 leaving the same remainder 12 in each case is 

a) 64     b)  124     c)  156      d) 260

Solution :

1356 - 12 ==> 1344

1868 - 12 ==> 1856

2764 - 12 ==> 2752

highest common factor = 2 x 2 x 2 x 2 x 2 x 2

= 64

Option a is correct.