Results 1 to 3 of 3

Thread: Euclidean Algorithm

  1. #1
    Newbie
    Joined
    Sep 2010
    Posts
    7

    Question Euclidean Algorithm

    Hey, I am having some trouble with an exercise.
    "Illustrate how the Euclidean Algorithm allows you to solve for intergers x, y such that 137x + 1000y = 1. You must show all the steps to demonstrate the use of the Euclidean Algorithm.

    Now I understand how to use the Algorithm to find the greatest common factor, but i am not sure what to do for this problem. Anyone have an idea?
    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2010
    Posts
    715
    Thanks
    2
    Say we want to find $\displaystyle \gcd(137, 1000)$. Then using Euclid's algorithm we have:

    $\displaystyle 1000 = (7)(137)+41 \Leftrightarrow 137 = (3)(41)+14 \Leftrightarrow 41 = (2)(14)+13 \Leftrightarrow 14 = (1)(13)+1. $

    So $\displaystyle \gcd(137, 1000) = 1$ (we knew that anyway). Working backwards systematically we have:

    $\displaystyle 1 = 14-1(13) = -41+3(14) = 3(137)-10(41) = 73(137)-10(1000).$

    So $\displaystyle x = 73$ and $\displaystyle y = -10$. See the proof of Bézout's Identity to see why we can find $\displaystyle x$ and $\displaystyle y$ this way.
    Last edited by TheCoffeeMachine; Sep 30th 2010 at 09:54 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2010
    Posts
    7
    that works, thank you =]
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Sep 14th 2010, 06:53 AM
  2. [SOLVED] Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: Sep 5th 2010, 06:45 PM
  3. GCD and the Euclidean Algorithm
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: Jan 3rd 2010, 03:20 AM
  4. Euclidean algorithm
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Aug 8th 2009, 08:28 AM
  5. Euclidean Algorithm
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 13th 2007, 07:20 AM

Search Tags


/mathhelpforum @mathhelpforum