Solving Linear Diophantine Equations: 158x-57y=7

[mlsbbe]

Homework Statement

Determine all solutions in positive integers of the following diaophantine equations

158x-57y=7

Homework Equations

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

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

This is apparently wrong. Can somebody help me?

 

[Dick]

-1 = 22*158 + 27*57 is pretty obviously silly. How did you get that?

 

[mlsbbe]

-1 = 22*158 + 27*57 is pretty obviously silly. How did you get that?

I know...I'm not too familiar with Euclid's Algorithm...that's why I'm asking for help. It looks a bit weird too... I think I might have a concept problem =(

 

[JSuarez]

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.

 

[mlsbbe]

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.

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?

 

[JSuarez]

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

 

[mlsbbe]

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

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.

 

[JSuarez]

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.