# 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 ->  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

 Ad: Algebrator™ solves your algebra problems and provides step-by-step explanations! Ad: Algebra Solved!™: algebra software solves algebra homework problems with step-by-step help!

 Algebra: Distributive, associative, commutative properties, FOIL Solvers Lessons Answers archive Quiz In Depth

 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.