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

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 correct
Answer 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

RELATED QUESTIONS
How do i show for intergers a,b and c from which at most one is 0(zero):... (answered by venugopalramana)

Calculate gcd(x,y) and express it as an integral linear combination of x and y. a)... (answered by venugopalramana)

How do i show for intergers a, b and k that gcd(a,b)= gcd(a,b+ka). Thank... (answered by venugopalramana)

Show for integers a,b and k that... (answered by venugopalramana)

For each of the following pairs a, b ∈ Z+, determine gcd(a, b) and express it as a (answered by goodman56)

Greatest Common Divisors and Least Common Multiples I need help with this guys,... (answered by Alan3354)

Show that gcd(a,gcd(b,c))=gcd(gcd(a,b),c) Ie show that gcd operator is associative (answered by Edwin McCravy)

I do not even know where to start with this proof. Prove or disprove: let a, b, and c... (answered by ikleyn)

Hello! I have problems proving that if {{{GCD (a, b) = 1}}} then {{{GCD (a * c, b) =... (answered by aaaaaaaa)