document.write( "Question 26635: Give the gcd(a,b) and integral linear combination of a and b
\n" ); document.write( "a=30031 and b=12449
\n" ); document.write( "I calculated the gcd to be 59 i am not sure if that is correct \n" ); document.write( "
Algebra.Com's Answer #14464 by venugopalramana(3286)\"\" \"About 
You can put this solution on YOUR website!
SEE THE FOLLOWING AND DO EXACTLY THE SAME WAY..IF YOU STILL HAVE DIFFICULTY COME BACK.
\n" ); document.write( "-----------------------------------------------------------------------
\n" ); document.write( "x=3113, y=1331
\n" ); document.write( "The gcd(3113,1331) is 451, but i don't know how to express as a integral combination of x and y.
\n" ); document.write( "GCD IS NOT 451 …IT IS 11…SEE BELOW.
\n" ); document.write( "1331 3113 2 ………….. ………….. ………….. ………….. …………..
\n" ); document.write( "………….. 451 1331 2 ………….. ………….. ………….. …………..
\n" ); document.write( "………….. ………….. 429 451 1 ………….. ………….. …………..
\n" ); document.write( "………….. ………….. ………….. 22 429 19 ………….. …………..
\n" ); document.write( "………….. ………….. ………….. ………….. 11 22 2 …………..
\n" ); document.write( "………….. ………….. ………….. ………….. ………….. 0 ………….. GCD=11
\n" ); document.write( "WE KNOW THAT IF N IS DIVIDED BY D TO GIVE QUOTIENT OF Q AND REMAINDER OF R THEN
\n" ); document.write( "N=Q*D+R….WE USE THIS TO WRITE GCD AS LINEAR COMBINATION OF THE 2 GIVEN NUMBERS.
\n" ); document.write( "THAT IS TO WRITE……….GCD = X * N1 + Y * N2
\n" ); document.write( "FROM THE ABOVE DIVISIONS WE DID TO FIND GCD,WE GET \r
\n" ); document.write( "\n" ); document.write( "3113=1331*2+451……OR……..451=3113 - 1331*2….……….I
\n" ); document.write( "1331=451*2+429………OR…….429 = 1331 - 451*2…...……..II
\n" ); document.write( "451=429*1+22…………OR……..22 = 451 - 429*1……...……..III
\n" ); document.write( "429=22*19+11…………OR……..11 = 429 - 22*19……….……..IV
\n" ); document.write( "22=11*2+0…………………………………………………………….V
\n" ); document.write( "HENCE GCD =11
\n" ); document.write( "WE NOW SUBSTITUTE BACK WARDS FROM EQN.IV TO EQN.I,REPLACING THE REMAINDERS IN EACH EQN.SUCCESSIVELY
\n" ); document.write( "11=429 - 22*19.................IV
\n" ); document.write( "= 429 - (451 - 429*1)*19 = 429 - 451*19+429*19= 429*20 - 451*19
\n" ); document.write( "=(1331 - 451*2)*20 - (3113 - 1331*2)*19 = 1331*20 - 451*40 -3113*19 + 1331*38 =1331*58 - 3113*19 - 451*40
\n" ); document.write( "=1331*58 - 3113*19 - (3113 - 1331*2)*40 = 1331*138 - 3113*59
\n" ); document.write( "HENCE GCD = 11 = 1331*138 - 3113*59
\n" ); document.write( "WHICH YOU CAN EASILY VERIFY.HOPE THE METHOD IS CLEAR.IT IS A BIT LONG PROCEDURE.
\n" ); document.write( "----------------------------------------------------------------------------
\n" ); document.write( "GCD OF 111 AND 126....GCD IS 3 AND 3 =126*15-111*17 AS SHOWN BELOW
\n" ); document.write( "111 126 1
\n" ); document.write( " 15 111 7
\n" ); document.write( " 6 15 2
\n" ); document.write( " 3 6 2
\n" ); document.write( " 0
\n" ); document.write( "
\n" ); document.write( " 15=6*2+3 ………….. 3=15-6*2
\n" ); document.write( " 111=15*7+6…………. 6=111-15*7
\n" ); document.write( " 126=111*1+15………. 15=126-111*1
\n" ); document.write( "
\n" ); document.write( " 3=15-6*2=15-(111-15*7)*2=15-{111-(126-111*1)*7}*2
\n" ); document.write( " =126-111*1-111*2+126*14-111*14
\n" ); document.write( " =126*15-111*17 \r
\n" ); document.write( "
\n" ); document.write( "\n" ); document.write( " \n" ); document.write( "
\n" );