Posted by Anonymous on Friday, September 28, 2012 at 9:54am.
Compute the GCD of 105 and 216 using thr Euclidean algorithm. A linear combination of 105 and 216 of the form
a 105 + b 216
can be reprented by the vector:
(a, b, a 105 + b 216)
We start with the two vectors:
v1 = (105, 0, 105)
v2 = (0,216, 216)
The integer part of 216/105 is 2.
v2 - 2 v1 = (-210, 216, 6)
We now define the new v2 to be the old v1 while the above vector becomes the new v1:
v1 = (-210, 216, 6)
v2 = (105, 0, 105)
We now repeat the previus step.
Integer part of 105/6 is 17.
v2 - 17 v1 = (3675, -3672, 3)
If you then would run another step, you would end up with a last component of zero, this means that the GCD is 3 and you have:
3 = 3675*105 - 3672*216
You can then add that last vector with zero last component to make the integers m and n positive.
Related Questions
math - there are three consecutive positive integers such that the sum of the ...
Math - Let a be an integer, then there are integers X, Y such that aX+(a+1)Y=1. ...
math, algebra - 2a+2ab+2b I need a lot of help in this one. it says find two ...
MATH - Find the only positive integer whose cube is the sum of the cubes of ...
Arithmetic Operations - Find a set of 4 distinct positive integers a,b,c,d such ...
Math - What is the smallest of 3 consecutive positive integers if the product of...
Math - What is the smallest of 3 consecutive positive integers if the product of...
arithmetic - Find the smallest positive integer P such that the cube root of 400...
Discrete Math - Theorem: For every integer n, if x and y are positive integers ...
Integers - The larger of two positive integers is five more than twice the ...
For Further Reading
