1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Extended Euclidean Algorithm

  1. Nov 2, 2011 #1
    1. The problem statement, all variables and given/known data

    There's a couple of questions that require the use of this, I'm having trouble with one of them, could anyone help?



    2. Relevant equations

    a) 520x - 1001y = 13
    b) 520x - 1001y = -26
    c) 520x - 1001y = 1


    3. The attempt at a solution

    The first two are easy to do,

    where you set 1001 and 520 as a and b respectively.

    so:

    1001 = 1*520 + 481
    520 = 1*481 + 39
    481 = 12*39 + 13
    39 = 3*13 + 0 for a)
    39 = 26 + 13 for b)


    And you use back-substitution for the first two and change the signs accordingly, that's fine,
    so you start with:
    a) 13 = 481 - (12*39)
    b) 26 = 39 - 13
    c) 1 = ?

    for c), I'm stumped. Do you use a fraction or something? or is there no solution? thanks for any help you can give me.
     
    Last edited: Nov 2, 2011
  2. jcsd
  3. Nov 2, 2011 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    The problem is that both 1001 and 520 are multiples of 13 (1001= 13(77), 520= 13(40) so that for any integer x and y, 520x+ 1001y= 13(77)x+ 13(40)y= 13(77x+ 40y) is a multiple of 13. 520x+ 1001y= A has a solution only if A is also a multiple of 13.

    In the first two problems, that is, of course, true and the first thing you would do is divide through by 13: 520x+ 1001y= 13==> 40x+ 77y= 1 and 520x+ 1001y= -26==> 40x+ 77y= -2.

    The third equation, 520x+ 1001y= 1 is not of that form. There are no solutions with integer x and y.
     
  4. Nov 3, 2011 #3
    Oh good, thanks for clarifying that, I had this suspicion that c) wasn't meant to have an answer.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Extended Euclidean Algorithm
  1. Euclidean Geometry (Replies: 1)

  2. Algorithm Time (Replies: 4)

  3. Division Algorithm (Replies: 3)

Loading...