Results 1 to 6 of 6

Math Help - Euclid Algorithm

  1. #1
    Newbie
    Joined
    Apr 2008
    Posts
    3

    Euclid Algorithm

    Urgent please help

    10010, 966 find the GCD

    What am i doing wrong?

    10010 = 966 x 10 + 350

    966 = 350 x 2 + 266

    350 = 266 x 1 + 84

    266 = 84 x 3 + 12

    84 = 12 x 7
    So 12 is the answer!?!
    Wrong answer though
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,689
    Thanks
    617
    Hello, Poolmaths!

    Your penultimate step . . .


    966 \;= \;84(3) + {\bf{\color{red}14}}
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2008
    Posts
    3
    266 not 966 in the penultimate step. any other ideas?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Dec 2007
    Posts
    131
    84=14\times6 after the correction, giving 14 as the correct answer.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Apr 2008
    Posts
    3

    New Question

    A follow on from the previous question.
    find integers x and y such that 10010x + 966y = 14

    having trouble working back.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Dec 2007
    Posts
    131
    answers =
    .
    .
    .
    (-149, 1544)
    (-80, 829)
    (-11, 114) This is the one you are looking for.
    (58, -601)
    (127,          -1316)
    .
    .
    .

    I cheated though. To help you do this by hand, try this link.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euclid Algorithm
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: January 15th 2012, 11:32 AM
  2. Euclid's Algorithm
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: March 29th 2009, 04:54 AM
  3. Finding GCD using Euclid's algorithm
    Posted in the Number Theory Forum
    Replies: 15
    Last Post: September 23rd 2008, 06:45 PM
  4. Another GCD using Euclid's Algorithm
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 23rd 2008, 09:03 AM
  5. Euclid's algorithm
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 3rd 2008, 05:18 AM

Search Tags


/mathhelpforum @mathhelpforum