Results 1 to 3 of 3

Math Help - Euclidean algorithm question help

  1. #1
    RAz
    RAz is offline
    Junior Member RAz's Avatar
    Joined
    May 2008
    From
    Canada
    Posts
    54

    Question [Solved, thanks Opalg :D] Euclidean algorithm question help

    Q: Find the HCF of the pair and express it in the form xa + yb = h

    966 and 1633

    I can find the HCF quite easily. I stuff up when "cleaning up" the equation.
    First of all: The final answer to this question is 23 = 22x966-13x1633

    My answer is different and here is how I got it:

    I got a HCF of 23 and by using the euclidean algorithm. I then showed:

    [..]Thus 966 = 1633 - 1x966 [1]
    667=966 - 1x667 [2]
    598=667 - 2x299 [3]
    276=299 - 4x69 [4]

    I now tried to express it in the form xa + yb = h

    23=299 - 4x69 [from 4]
    =299 - 4(667 - 2x299) [from 3]
    =3x299 - 4x667
    =3(966 - 1x667) - 4x667 [from 2]
    =3x966 - 7x667
    =3x966 - 7(1633 - 1x966)
    Therefore =11x966 - 7x1633

    Now that is obviously wrong, but I don't know where or how the mistake I made occurred. I hate when I spend ages on a question and it turns out wrong. It lowers my self esteem
    Last edited by RAz; March 14th 2009 at 08:44 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by RAz View Post
    Q: Find the HCF of the pair and express it in the form xa + yb = h

    966 and 1633

    I can find the HCF quite easily. I stuff up when "cleaning up" the equation.
    First of all: The final answer to this question is 23 = 22x966-13x1633

    My answer is different and here is how I got it:

    I got a HCF of 23 and by using the euclidean algorithm. I then showed:

    [..]Thus 667 = 1633 - 1x966 [1]
    299=966 - 1x667 [2]
    69=667 - 2x299 [3]
    23=299 - 4x69 [4]

    I now tried to express it in the form xa + yb = h

    23=299 - 4x69 [from 4]
    =299 - 4(667 - 2x299) [from 3]
    =9x299 - 4x667
    =9(966 - 1x667) - 4x667 [from 2]
    =9x966 - 13x667
    =9x966 - 13(1633 - 1x966)
    Therefore =22x966 - 13x1633

    Now that is obviously wrong, but I don't know where or how the mistake I made occurred. I hate when I spend ages on a question and it turns out wrong. It lowers my self esteem
    The method is correct, it's just the arithmetic that is all wrong. See corrections in red above.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    RAz
    RAz is offline
    Junior Member RAz's Avatar
    Joined
    May 2008
    From
    Canada
    Posts
    54
    Thankyou for your help, this is very useful
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euclidean Algorithm
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: December 5th 2011, 05:59 AM
  2. Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 24th 2010, 09:54 PM
  3. Euclidean algorithm
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: January 19th 2010, 11:13 AM
  4. Euclidean algorithm
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: August 8th 2009, 08:28 AM
  5. Euclidean algorithm gcd lcm help..
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 10th 2006, 05:46 AM

Search Tags


/mathhelpforum @mathhelpforum