Results 1 to 3 of 3

Math Help - Euclidean Algorithm - Linear Combination

  1. #1
    Member
    Joined
    Jul 2008
    Posts
    119

    Euclidean Algorithm - Linear Combination

    Problem:
    Use the Euclidean Algorithm, find the gcd of 330 and 126 and write it as a linear combination of the two numbers.

    ===============
    Attempt:
    Using the Euclidean Algorithm, we need to find (330, 126)

    330 = 126 * 2 + 78 (5)
    126 = 78 * 1 + 48 (4)
    78 = 48 * 1 + 30 (3)
    30 = 18 * 1 + 12 (2)
    18 = 12 * 1 + 6 (1)
    12 = 6 * 2 + 0, Thus the gcd = 6. As a result, (330, 126)= 6.

    Following the extended Euclidean Algorithm, so I do it solve for '6' backwards.

    From (1), 18 = 12 * 1 + 6. I solve for 6. Thus

    6 = 18 - 12 * 1 (A)

    From (2), solve for 12, we get

    12 = 30 - 18 * 1 (B)

    Plug 12 from (B) to A we get 6 = 18 - (30 - 18*1)

    Likewise, we get

    6 = 18 - (30 - (48 - 30))... and so on.

    where I need to get it in the form

    6 = 330x + 126y, where x and y are integers.
    ==================
    Is there a way to find the linear combination faster or better? Thank you.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by Paperwings View Post
    Problem:
    Use the Euclidean Algorithm, find the gcd of 330 and 126 and write it as a linear combination of the two numbers.

    ===============
    Attempt:
    Using the Euclidean Algorithm, we need to find (330, 126)

    330 = 126 * 2 + 78 (5)
    126 = 78 * 1 + 48 (4)
    78 = 48 * 1 + 30 (3)
    30 = 18 * 1 + 12 (2)
    18 = 12 * 1 + 6 (1)
    12 = 6 * 2 + 0, Thus the gcd = 6. As a result, (330, 126)= 6.

    Following the extended Euclidean Algorithm, so I do it solve for '6' backwards.

    From (1), 18 = 12 * 1 + 6. I solve for 6. Thus

    6 = 18 - 12 * 1 (A)

    From (2), solve for 12, we get

    12 = 30 - 18 * 1 (B)

    Plug 12 from (B) to A we get 6 = 18 - (30 - 18*1)

    Likewise, we get

    6 = 18 - (30 - (48 - 30))... and so on.

    where I need to get it in the form

    6 = 330x + 126y, where x and y are integers.
    ==================
    Is there a way to find the linear combination faster or better? Thank you.
    see post #8 here. i described the method you're using and a method that i think is better/faster. with this method, you find the gcd and the linear combination all in one shot
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jul 2008
    Posts
    119
    Thanks Jhevon. I'll give it a try.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 30th 2010, 10:46 AM
  2. [SOLVED] Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 5
    Last Post: September 5th 2010, 06:45 PM
  3. Euclidean Algorithm
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 13th 2010, 07:25 PM
  4. GCD and the Euclidean Algorithm
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: January 3rd 2010, 03:20 AM
  5. Euclidean Algorithm
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: May 7th 2006, 11:25 AM

Search Tags


/mathhelpforum @mathhelpforum