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