Question

Find the HCF of the following pairs of integers and express it as a linear combination of 592 and 252.

Answer 1

By applying Euclid’s division lemma

595 = 252 × 2 + 91 ….. (i)

Since remainder ≠ 0, apply division lemma on divisor 252 and remainder 91

252 = 91 × 2 + 70 …. (ii)

Since remainder ≠ 0, apply division lemma on divisor 91 and remainder 70

91 = 70 × 1 + 21 ….(iii)

Since remainder ≠ 0, apply division lemma on divisor 70 and remainder 20

70 = 21 × 3 + 7 …..(iv)

Since remainder ≠ 0, apply division lemma on divisor 21 and remainder 7

21 = 7 × 3 + 0

H.C.F = 7

Now, 7 = 70 – 21 × 3 [from (iv)]

= 70 – [90 – 70 × 1] × 3 [from (iii)]

= 70 – 91 × 3 + 70 × 3

= 70 × 4 – 91 × 3

= [252 – 91 × 2] × 4 – 91 × 3 [from (ii)]

= 252 × 4 – 91 × 8 – 91 × 3

= 252 × 4 – 91 × 11

= 252 × 4 – [595 – 252 × 2] × 11 [from (i)]

= 252 × 4 – 595 × 11 + 252 × 22

= 252 × 6 – 595 × 11