Question

Find the hcf of 55 and 210. express it as linear combination of 55 and 210 i.e HCF of 55 and 210 = 210a +55b, for some a and b ?

Answer 1

SOLUTION:

Here,

55 < 210

So,

By applying Euclid's Division Lemma(EDL), we will get,

210 = (55 * 3) + 45 ......(i)

But here the remainder is 45 ≠ 0.

Now,

The new dividend is 55 and

The new divisor is 45

By applying EDL, we will get,

55 = (45 * 1) + 10  .......(ii)

Here,

The remainder is 10 ≠ 0.

Again,

The new dividend is 45 and

The new divisor is 10

By applying EDL, we will get,

45 = (10 * 4) + 5  .......(iii)

Again here,

The remainder is 5 ≠ 0.

So,

The new dividend is 10 and

The new divisor is 5

By applying EDL, we will get,

10 = (5 * 2) + 0

Here,

The remainder is 0

Hence,

The HCF of 210 and 55 is 5.

[As 5 was the last divisor]

Now,

As to express the HCF as a linear combination of the two given numbers, we will start with the equation(iii)

From equation(iii), 5 = 45 - (10 * 4)

⇒ 5 = 45 - [55 - 45 * 1) * 4]

[∵ we get from equation(ii) → 55 - (45 * 1) = 10]

⇒ 5 = 45 - 55 * 4 + 45 * 4

⇒ 5 = 5 *45 - 55 * 4

[From the equation(i) → 210 - (55 * 3) = 45]

⇒ 5 = 5 * (210 - 55 * 3) - 55 * 4

⇒ 5 = 210 * 5 - 55 * 19

⇒ 5 = 210a + 55b

Where, a = 5 and b = -19