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