If d is the HCF of 30, 72, find the value of x & y satisfying d = 30x + 72y.

Ans:  Using Euclid’s algorithm, the HCF (30, 72)

  72 = 30 × 2 + 12
  30 = 12 × 2 + 6
  12 = 6 × 2 + 0

HCF (30,72) = 6
6=30-12×2
6=30-(72-30×2)2
6=30-2×72+30×4
6=30×5+72×-2
∴ x = 5, y = -2

Also 6 = 30 ×5 + 72 (-2) + 30 × 72 – 30 × 72

  Solve it, to get

      x = 77, y = -32

Hence, x and y are not unique