If d is the H.C.F of 30 and 72. Find the value of x and y satisfying d = 30x + 72y.

The given numbers are 30 and 72 and according to the EUCLID'S DIVISION lemma:

Given two positive integers a and b, there exist unique integers q and r satisfying a = bq + r, such that 0 ≤ r < b and a, b are two numbers.

Since 72 > 30

72 = 30 × 2 + 12 …… eq (1)

30 = 12 × 2 + 6 ……eq (2)

12 = 6 × 2 + 0 ……eq (3)

Since the remainder has now become zero, the divisor is 6, and therefore the H.C.F is 6

From eq(2) we get that,

30 = 12 × 2 + 6

Rearranging the terms,

6 = 30 – 12 × 2

⇒ 6 = 30 – (72 – 30 × 2 ) × 2 ]

⇒ 6 = 30 – 72 × 2 + 4 × 30 [using distributive property ]

⇒ 6 = 30 × (1+ 4 ) + 72 × (–2 )

⇒ 6 = 30 × 5 + 72 × (–2) ……(4)

According to the problem,

d = 30x + 72y ……(5)

Compare (4) and (5 ),

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

x = 5 and y = –2