1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: Linear Diaophantine Equations

  1. Feb 7, 2010 #1
    1. The problem statement, all variables and given/known data

    Determine all solutions in positive integers of the following diaophantine equations


    2. Relevant equations

    3. The attempt at a solution

    I've been trying to solve the linear diophantine equation, but to no avail:

    158x-57y = 7.

    I've used Euclid's algorithm to get

    gcd = -1

    -1 = 22*158 + 27*57

    -1*7= -154*158 - 184*57

    This is apparently wrong. Can somebody help me?
  2. jcsd
  3. Feb 7, 2010 #2


    User Avatar
    Science Advisor
    Homework Helper

    -1 = 22*158 + 27*57 is pretty obviously silly. How did you get that?
  4. Feb 7, 2010 #3
    I know...I'm not too familiar with Euclid's Algorithm....that's why I'm asking for help. It looks a bit wierd too.... I think I might have a concept problem =(
  5. Feb 7, 2010 #4
    To state again that something is obviously wrong, note that the gcd is, by definition positive, so there's something wrong in your application of the first passage of the algorithm. From the equation, the gcd can only be either 1 or 7; as 7 doesn't divide 57, it must be 1.
  6. Feb 8, 2010 #5
    Actually I'm having trouble applying Euclid's Algorithm here in this case. Most examples are done using with the form ax+by =c. In the case here, the "+" sign is now a "-". Can anybody point me in the general direction or give me a link on how to do this?
  7. Feb 8, 2010 #6
    But it's the same. The Euclidian algorithm doesn't depend on the signs: the first passage is just integer divisions, which may be applied to positive and negative integers. It seems that you went wrong when calculating the remainder, that is always positive. Recall that the division theorem states that:

    a = bq + r, 0 <= r < |b|

    Didn'n you forget the modulus? I'll give you the first division:

    gcd(158,-57) = gcd(-57,44) 158 = (-2)*(-57) + 44, 0 <= 44 < |-57|=57
  8. Feb 9, 2010 #7
    I've made an attempt. I don't think I seem to be getting this right....can somebody check to see if I'm getting anything wrong?

    (-57)*(-2) + 44 =158

    (44)*(-2) + 31 = -57

    (31)*(1) + 13 = 44

    (13)*(2) + 5 =31

    (5)*(2) + 3 =13

    (3)*(1) + 2 =5

    (1)*(2) +1= 3

    gcd(a,b) = 1

    Apparently, the answer is

    x=17 and y = 47

    Since x = 17 is prime, then I am wondering if the answer is wrong, since you must multiply the gcd by 7 to get the answer.
  9. Feb 9, 2010 #8
    No, x = 17 and y = 47 is indeed a solution, but these equations, if they have a solution, then they have an infinite number of them. This means that that particular solution was obtained by a different method. And your divisions are, as far as I can see, correct; if you now compute the ascending part of the euclidian algorithm, you should also obtain a solution, albeit a different one.

    Here's another suggestion: if you are more confortable with equations in the form ax+by=c, then simply take your equation 158x-57y=7 and rewrite as 158x+57(-y)=7 and solve it for x and y'=-y.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook