  Question

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

Solution

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.  Mathematics

Suggest Corrections  0  Similar questions
View More  People also searched for
View More 