Question

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

Answer 1

EUCLID'S DIVISION ALGORITHM:

Given positive integers a and b , there exist unique integers q and r satisfying

a = bq + r ,

0 ≤ r < b

*************************************************************************************

Applying Euclid's division lemma to 30 and 72

Since 72 > 30

72 = 30 × 2 + 12 ------------( 1 )

30 = 12 × 2 + 6 ------------( 2 )

12 = 6 × 2 + 0 -----------( 3 )

The remainder has now become zero,

Since the divisor at this stage is 6 ,

The HCF of 30 and 72 = 6

now from ( 2)

30 = 12 × 2 + 6

Rearrange this

6 = 30 - 12 × 2

⇒ 6 = 30 - [ (72 - 30 × 2 ) × 2 ] { from ( 1 ) }

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

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

according to the problem ,

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

compare ( 4 ) and ( 5 ) ,

x = 5 and y = -2

Note : these x , y values are not unique.