How can I solve diophantine equations effectively?

[The legend]

Which is the best way to solve diophantine equations? I have tried out a few but I'm not just getting the hang of it.

example

ax + by = 1

 

[CRGreathouse]

In general, Diophantine equations are very hard or impossible to solve. For this one, I suggest
http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

 

[G037H3]

there is no universal method to solve them :3

simple linear form, in your OP, does have at least one algorithm though

 

[The legend]

In general, Diophantine equations are very hard or impossible to solve. For this one, I suggest
http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

oh thanks!

too bad they are very hard (or impossible)... maybe that's why they are asked in olympiads!

 

[The legend]

there is no universal method to solve them :3

simple linear form, in your OP, does have at least one algorithm though

say instead of linear form we take in the quadratic form, then does it have any algorithm?

 

[CRGreathouse]

say instead of linear form we take in the quadratic form, then does it have any algorithm?

Yes. In two variables, see
http://www.alpertron.com.ar/QUAD.HTM

 

[HallsofIvy]

linear Diophantine equations, which is what the OP seems to be talking about, are fairly simple and straight forward.

Given ax+ by= c.

If a and b have a common factor that does NOT divide c, there is no solution. That is because, for any x and y, the left side will be a multiple of that common factor.

If a, b, and c all have a common factor we can divide through by that factor to get a simpler equation.

So we can assume that a and b are relatively prime.

In that case, the Euclidean division algorithm shows that there exist $x_0$ and $y_0$ so that $ax_0+ by_0= 1$. Multiply by c to get $a(cx_0)+ b(cy_0)= c$. $cx_0$ and $cy_0$ are solutions.

It is also easy to see that if x and y are integer solutions to ax+ by= c, then x+ bk and y- ak are also solutions: a(x+ bk)+ b(y- ak)= ax+ abk+ by- abk= ax+ by= c.

For example, to solve 4x+ 7y= 15, I note that 4 divides into 7 once with remainder 3. that is, 7- 4= 3. Also 3 divides into 4 once with remainder 1: 4- 3= 1. Replace the "3" in the last equation with 7- 4 to get 4- (7- 4)= 1 or 2(4)- 1(7)= 1. Multiplying by 15, 30(4)- 15(7)= 15. That is, one solution is x= 30, y= -15. All solutions are of the form x= 30+ 7k, y= -15- 4k for some integer k. If you want positive solutions, then we note that in order that y be positive, we must have -15- 4k> 0 or -4k> 15 which means that the integer k must be less than or equal to -4. Taking k= -4 gives x= 30+7(-4)= 2 and y= -15+ 4(-4)= 1. Any k larger than -4 makes y negative and any k less than -4 make x negative. The only positive solution to 4x+7y= 15 is x= 2, y= 1.

 

[The legend]

linear Diophantine equations, which is what the OP seems to be talking about, are fairly simple and straight forward.

Given ax+ by= c.

If a and b have a common factor that does NOT divide c, there is no solution. That is because, for any x and y, the left side will be a multiple of that common factor.

If a, b, and c all have a common factor we can divide through by that factor to get a simpler equation.

So we can assume that a and b are relatively prime.

In that case, the Euclidean division algorithm shows that there exist $x_0$ and $y_0$ so that $ax_0+ by_0= 1$. Multiply by c to get $a(cx_0)+ b(cy_0)= c$. $cx_0$ and $cy_0$ are solutions.

It is also easy to see that if x and y are integer solutions to ax+ by= c, then x+ bk and y- ak are also solutions: a(x+ bk)+ b(y- ak)= ax+ abk+ by- abk= ax+ by= c.

For example, to solve 4x+ 7y= 15, I note that 4 divides into 7 once with remainder 3. that is, 7- 4= 3. Also 3 divides into 4 once with remainder 1: 4- 3= 1. Replace the "3" in the last equation with 7- 4 to get 4- (7- 4)= 1 or 2(4)- 1(7)= 1. Multiplying by 15, 30(4)- 15(7)= 15. That is, one solution is x= 30, y= -15. All solutions are of the form x= 30+ 7k, y= -15- 4k for some integer k. If you want positive solutions, then we note that in order that y be positive, we must have -15- 4k> 0 or -4k> 15 which means that the integer k must be less than or equal to -4. Taking k= -4 gives x= 30+7(-4)= 2 and y= -15+ 4(-4)= 1. Any k larger than -4 makes y negative and any k less than -4 make x negative. The only positive solution to 4x+7y= 15 is x= 2, y= 1.

Wow! getting the hang of it!
Thanks a lot!
the example did make it quite clear.

 

[The legend]

Yes. In two variables, see
http://www.alpertron.com.ar/QUAD.HTM

nice step by step solutions.
The method for different types of quadratics is also very very cool

Thanks!

I got another link which i found useful which determines whether the equation can be solved or not(Hilbert's Tenth Problem)

http://www.ltn.lv/~podnieks/gt4.html

 

[epsi00]

nice step by step solutions.
The method for different types of quadratics is also very very cool

Thanks!

I got another link which i found useful which determines whether the equation can be solved or not(Hilbert's Tenth Problem)

http://www.ltn.lv/~podnieks/gt4.html

Well, here's another site which solves linear diophantine equation:

http://www.math.uwaterloo.ca/~snburris/htdocs/linear.html

but it's better to use Alperton site since it does linear equation too and even give you the verbose from which you can learn

 

[The legend]

Well, here's another site which solves linear diophantine equation:

http://www.math.uwaterloo.ca/~snburris/htdocs/linear.html

but it's better to use Alperton site since it does linear equation too and even give you the verbose from which you can learn

The alperton site does that too ... just click on step-by-step solutions and voila! You get exactly how the sum is solved. Also the Alperton site has 2 degree equations instead of this one which contains only 1st degree equations.