# 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) + 72y72y = 4 - 5672y = - 52y is not integer. If x = 24 = 56(2) + 72y72y = 4 - 11272y = - 108y 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. ### Finding Range of Values Inequality Problems

May 21, 24 08:51 PM

Finding Range of Values Inequality Problems

Read More

2. ### Solving Two Step Inequality Word Problems

May 21, 24 08:51 AM

Solving Two Step Inequality Word Problems

Read More

3. ### Exponential Function Context and Data Modeling

May 20, 24 10:45 PM

Exponential Function Context and Data Modeling

Read More