Question

If d is the HCF of 30 and 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.

Answer 2

Answer:

Explanation:

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