Question

7. If H is the HCF of two positive integers a and b, then there exist two integers X and Y such that

a) a = XH + Yb

b) b = Xa + YH

c) H = Xa + Yb

d) none of these

Standard:- 10

No Spamming

Answer 1

Here is your solution :

Given,

H is the H.C.F of two positive numbers a and b , there exists two numbers X and Y.

Euclid's Division Lenma : It states that if a and b are two positive numbers such that a > b , then there exists two numbers q and r ( 0 ≤ r < b ).

=> a = bq + r

Using Euclid's Division Lenma ,

Suppose, a = 5 and b = 3.

First step :

=> 5 = ( 3 × 1 ) + 2

Second Step :

=> 3 = ( 2 × 1 ) + 1

Third step :

=> 2 = ( 1 × 2 ) + 0

Hence, 1 is the H.C.F of a and b i.e. H.

FromSecond step :

=> 3 - ( 2 × 1 ) = 1. -------- ( 1 )

From first step :

=> 5 = ( 3 × 1 ) + 2

=> ( 5 - 3 × 1 ) = 2

Substitute this value in ( 1 ),

=> 3 - [ ( 5 - 3 × 1 ) × 1 ] = 1

=> 3 - ( 5 × 1 ) - ( -3 × 1 × 1 ) = 1

=> 3 - ( 5 × 1) + ( 3 × 1 ) = 1

=> 3 + ( 3 × 1 ) - ( 5 × 1 ) = 1

=> 3 ( 1 + 1 ) - 5 × 1 = 1

=> ( 3 × 2 ) + [ 5 × ( -1 ) ] = 1

Now,

Suppose X = ( -1 ) and Y = 2

=> 3Y + 5X = 1

Now, substitute the value of 3,5 and 1.

=> bY + aX = H

•°• Xa + Yb= H.

Hence, the required answer is

c. ) H = Xa + Yb.

Hope it helps !!