# SOLUTION: Give the gcd(a,b) and integral linear combination of a and b a=30031 and b=12449 I calculated the gcd to be 59 i am not sure if that is correct

Algebra ->  Algebra  -> Distributive-associative-commutative-properties -> SOLUTION: Give the gcd(a,b) and integral linear combination of a and b a=30031 and b=12449 I calculated the gcd to be 59 i am not sure if that is correct      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 26635: Give the gcd(a,b) and integral linear combination of a and b a=30031 and b=12449 I calculated the gcd to be 59 i am not sure if that is correctAnswer by venugopalramana(3286)   (Show Source): You can put this solution on YOUR website!SEE THE FOLLOWING AND DO EXACTLY THE SAME WAY..IF YOU STILL HAVE DIFFICULTY COME BACK. ----------------------------------------------------------------------- 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. ---------------------------------------------------------------------------- GCD OF 111 AND 126....GCD IS 3 AND 3 =126*15-111*17 AS SHOWN BELOW 111 126 1 15 111 7 6 15 2 3 6 2 0 15=6*2+3 .. 3=15-6*2 111=15*7+6. 6=111-15*7 126=111*1+15. 15=126-111*1 3=15-6*2=15-(111-15*7)*2=15-{111-(126-111*1)*7}*2 =126-111*1-111*2+126*14-111*14 =126*15-111*17