Math Help - Linear diaphantine equations

1. Linear diaphantine equations

Do diophantine equations ax+by =C with gcd (a,b) = 1 have a solution?
Consider the following diophantine equations
30x + 17y = 30
158x-57y=7

gcd of both these equations are 1. So does that mean these equations have no solution?

2. Dear mlsbbe,

The diaphantine equation, $ax+by=c$ have solutions iff $(a,b)\mid{c}$. So in your case (a,b)=1 and since $1\mid{c},~ ax+by=c$ have solutions.

Therefore 30x + 17y = 30 and 158x-57y=7 have solutions.

Hope this helps.

3. 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?

4. Originally Posted by mlsbbe
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?
Dear mlsbbe,

First of all (a,b)=d (the greatest common divisor of a and b is d) means the greatest positive integer that divides both a and b is d. Therefore by definition the greatest common divisor is always positive.

When finding the greatest common divisor and the general solution to a Diophantine equation use the method I have given below.

$158x-57y = 7$

Using Euclid's algorithm,

Since 158>57

$158=(57\times{2})+44$

57>44

$57=(44\times{1})+13$

44>13

$44=(13\times{3})+5$

13>5

$13=(5\times{2})+3$

5>3

$5=(3\times{1})+2$

3>2

$3=(2\times{1})+1$

Therefore, (158,57)=1

Now using reverse substitution,

$1=3-2$

$1=3-(5-3)=-5+(2\times{3})$

$1=-5+2{13-(5\times{2})}=(-5\times{5})+(2\times{13})$

$1=(2\times{13})-5[44-(13\times{3})]=(17\times{13})-(5\times{44})$

$1=(-5\times{44})+17[57-44]=(-22\times{44})+(17\times{57})$

$1=(17\times{57})-22[158-(57\times{2})]=(61\times{57})-(22\times{158})$

$7=(158\times{(-22\times7)})-(57\times{(-61\times{7})})$

Therefore, $x=-154~and~y=-427~is~a~particular solution.$

The general solution,

$x=-154-57t~and~y=-427-158t~;~t\in{Z}$

5. Originally Posted by mlsbbe
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
What? The sum of two positive numbers cannot be -1!
At first I thought perhaps you just had a sign wrong but
22*158= 3476 and 27*57= 1539. They are not even close!

Try again.

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

This is apparently wrong. Can somebody help me?