SOLUTION: Calculate gcd(x,y) and express it as an integral linear combination of x and y.
a) x=3113, y=1331
The gcd(3113,1331) is 451, but i don't know how to express as a integral combi
Algebra ->
Distributive-associative-commutative-properties
-> SOLUTION: Calculate gcd(x,y) and express it as an integral linear combination of x and y.
a) x=3113, y=1331
The gcd(3113,1331) is 451, but i don't know how to express as a integral combi
Log On
Question 26383: Calculate gcd(x,y) and express it as an integral linear combination of x and y.
a) x=3113, y=1331
The gcd(3113,1331) is 451, but i don't know how to express as a integral combination of x and y. Answer by venugopalramana(3286) (Show Source):
You can put this solution on YOUR website!
x=3113, y=1331
The gcd(3113,1331) is 451, but i don't know how to express as a integral combination of x and y.
GCD IS NOT 451 IT IS 11 SEE BELOW.
1331 3113 2 .. .. .. .. ..
.. 451 1331 2 .. .. .. ..
.. .. 429 451 1 .. .. ..
.. .. .. 22 429 19 .. ..
.. .. .. .. 11 22 2 ..
.. .. .. .. .. 0 .. GCD=11
WE KNOW THAT IF N IS DIVIDED BY D TO GIVE QUOTIENT OF Q AND REMAINDER OF R THEN
N=Q*D+R .WE USE THIS TO WRITE GCD AS LINEAR COMBINATION OF THE 2 GIVEN NUMBERS.
THAT IS TO WRITE .GCD = X * N1 + Y * N2
FROM THE ABOVE DIVISIONS WE DID TO FIND GCD,WE GET
3113=1331*2+451 OR ..451=3113 - 1331*2 . .I
1331=451*2+429 OR .429 = 1331 - 451*2 ... ..II
451=429*1+22 OR ..22 = 451 - 429*1 ... ..III
429=22*19+11 OR ..11 = 429 - 22*19 . ..IV
22=11*2+0 .V
HENCE GCD =11
WE NOW SUBSTITUTE BACK WARDS FROM EQN.IV TO EQN.I,REPLACING THE REMAINDERS IN EACH EQN.SUCCESSIVELY
11=429 - 22*19.................IV
= 429 - (451 - 429*1)*19 = 429 - 451*19+429*19= 429*20 - 451*19
=(1331 - 451*2)*20 - (3113 - 1331*2)*19 = 1331*20 - 451*40 -3113*19 + 1331*38 =1331*58 - 3113*19 - 451*40
=1331*58 - 3113*19 - (3113 - 1331*2)*40 = 1331*138 - 3113*59
HENCE GCD = 11 = 1331*138 - 3113*59
WHICH YOU CAN EASILY VERIFY.HOPE THE METHOD IS CLEAR.IT IS A BIT LONG PROCEDURE.
