Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: 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
    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.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook