Question

If d is the Highest Common Factor of 32 and 60, find x and y satisfying d = 32x + 60y

Answer 1

Applying Euclid’s divison lemma to 32 and 60, we get

60 = 32 × 1 + 28   ...(i)

The remainder is 28 ≠ 0.

Again applying division lemma

32 = 28 × 1 + 4  ...(ii)

The remainder 4 ≠ 0.

Again applying division lemma

28 = 4 × 7 + 0  ...(iii)

The remainder zero.

∴ H.C.F. of 32 and 60 is 4.

From (ii), we get

32 = 28 × 1 + 4

⇒ 4 = 32 – 28 × 1

⇒ 4 = 32 – (60 – 32 × 1) × 1

⇒ 4 = 32 – 60 + 32

⇒ 4 = 32 × 2 + (– 1) × 60

∴ x = 2 and y = – 1