Results 1 to 4 of 4

Math Help - Euclidean Algorithm

  1. #1
    Junior Member
    Joined
    Mar 2009
    Posts
    62

    Euclidean Algorithm

    Using the Euclidean Algorithm to solve 13 in Z30

    30 = 2x13+4
    13= 3x4+1

    Eliminating multiples of four

    1= 13-3x4
    = 13-3(30-2x13)
    = 7x13-3x30 ---- How was this achieved?

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    13-3(30-2 \cdot 13) = 13-(3 \cdot 30 - 6 \cdot 13) = 13 - 3 \cdot 30 + 6 \cdot 13 = (6+1) \cdot 13 - 3 \cdot 30 = 7 \cdot 13 - 3 \cdot 30
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,713
    Thanks
    1472
    Quote Originally Posted by mark090480 View Post
    Using the Euclidean Algorithm to solve 13 in Z30

    30 = 2x13+4
    13= 3x4+1

    Eliminating multiples of four

    1= 13-3x4
    = 13-3(30-2x13)
    = 13- 3(30)- 3(-2(13))= 13- 3(30)+ 6(13)= 7(13)- 3(30)

    = 7x13-3x30 ---- How was this achieved?

    Thanks
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Mar 2009
    Posts
    62
    Could you explain what is going on here? I don't understand why we do it in that way. My maths books just tells me how and not why. Thanks.
    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. 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