Saturday

April 19, 2014

April 19, 2014

Posted by **Anonymous** on Friday, September 28, 2012 at 9:54am.

- Math -
**Anonymous**, Friday, September 28, 2012 at 2:52pmCompute 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**

arithmetic - Find the smallest positive integer P such that the cube root of 400...

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 - Find the smallest positive integer n such that the equation 455x+1547y=50...

Algebra - Find the smallest positive integer N such that 13^N \equiv 1 \pmod{...

maths - if Kis the smallest positive integer such that(2k)(5200) has 303digits. ...

maths - if Kis the smallest positive integer such that(2k)(5200) has 303digits. ...

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

Algebra - Find the smallest positive integer N \neq 23 such that the fraction \...