Results 1 to 3 of 3

Math Help - 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 \gcd(137, 1000). Then using Euclid's algorithm we have:

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

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

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

    So x = 73 and y = -10. See the proof of Bézout's Identity to see why we can find x and y this way.
    Last edited by TheCoffeeMachine; September 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: September 14th 2010, 06:53 AM
  2. [SOLVED] Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: September 5th 2010, 06:45 PM
  3. GCD and the Euclidean Algorithm
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: January 3rd 2010, 03:20 AM
  4. Euclidean algorithm
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: August 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