EXPRESSING THE HCF OF TWO NUMBERS AS LINEAR COMBINATION

Using division algorithm, we may express HCF of two numbers as linear combination.

Step 1 :

In the given numbers, choose the larger number one.

Step 2 :

Decompose the larger one by the multiple of smaller one.

Step 3 :

Step 2 will have the form,

Divided = Divisor x quotient + Remainder

Repeat the process until we receive remainder as 0.

At last by dividing which value, we get the remainder as 0, that can be considered as HCF of the given numbers.

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

If x = 1

4 = 56(1) + 72y

72y = 4 - 56

72y = - 52

y is not integer.

If x = 2

4 = 56(2) + 72y

72y = 4 - 112

72y = - 108

y is not integer.

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.

Recent Articles

  1. Graphing Exponential Growth and Decay Worksheet

    Dec 08, 23 08:03 AM

    graphing-exponential-growth-and-decay-s1
    Graphing Exponential Growth and Decay Worksheet

    Read More

  2. Finding the Specific Term from the Given Explicit Formula Worksheet

    Dec 08, 23 07:32 AM

    Finding the Specific Term from the Given Explicit Formula Worksheet

    Read More

  3. Finding Roots of Complex Numbers Using De Moivres Theorem Worksheet

    Dec 08, 23 07:10 AM

    Finding Roots of Complex Numbers Using De Moivres Theorem Worksheet

    Read More