Results 1 to 3 of 3

Math Help - Number Theory GCD Linear Combination

  1. #1
    Junior Member
    Joined
    Jun 2008
    Posts
    27

    Number Theory GCD Linear Combination

    Hi again (as you can tell, I've been working on this stuff all day, sorry for posting so much!)

    Right now I'm working on a Linear Combinations problem.

    Here's the problem:
    Write GCD(1326,252) as a linear combination of 1326 and 252.

    Here's what I have:

    Find the GCD:
    1326 = 5 * 252 + 66
    252 = 3 * 66 + 58
    66 = 1 * 58 + 8
    58 = 7 * 8 + 2
    8 = 4 * 2 + 0 so 2 is the GCD

    Now work backwards:
    2 = 58 - 7 * 8
    8 = 66 - 1 * 58
    58 = 252 - 3 * 66
    66 = 1326 - 5 * 252

    Substitute: *this is where I'm having problems!
    2 = 58 - 7 * 8
    = 58 - 7 * ( 66 - 1 * 58 )
    = 8 ( 58 ) - 7 ( 66 ) <--- but I need it in 1326,252 form, so I continue...
    = 8 ( 252 - 3 * 66 ) - 7 ( 1326 - 5 * 252 )
    = 8 ( 252 - 3 ( 1326 - 5 * 252 ) - 7 ( 1326 - 5 * 252 )
    = 8 ( 252 ) - 24 ( 1326 - 5 * 252 ) - 7 ( 1326 ) + 35 ( 252 )
    = 8(252) -24(1326) +120(252) -7(1326) +35(252)
    = 163(252) -31(1326) // simplified
    = -31(1326) +163(252) // swapped sides

    But this equals 30 so I am messing up somewhere.
    It should equal 2 right? I can't figure out where I got the +28
    Follow Math Help Forum on Facebook and Google+

  2. #2
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407
    Unfortunately early in your steps: 252 \neq 3(66) + 58 but rather 252 = 3(66) + 54
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jun 2008
    Posts
    27
    Actually, you know, that's a relief because it means the process is probably ok. I thought I was really messing up somewhere.. a miscalculation is GREAT!

    Thanks again o_O
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Total number of combinations for combination lock
    Posted in the Advanced Statistics Forum
    Replies: 6
    Last Post: December 26th 2011, 10:11 AM
  2. Textbooks on Galois Theory and Algebraic Number Theory
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: July 8th 2011, 06:09 PM
  3. Replies: 2
    Last Post: December 18th 2008, 05:28 PM
  4. Linear Algebra - Linear Combination/Span
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 13th 2008, 06:06 PM
  5. number of combination of 8 digits number
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 7th 2008, 03:37 AM

Search Tags


/mathhelpforum @mathhelpforum