- 421
- 0
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
example
ax + by = 1
oh thanks!In general, Diophantine equations are very hard or impossible to solve. For this one, I suggest
http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
say instead of linear form we take in the quadratic form, then does it have any algorithm?there is no universal method to solve them :3
simple linear form, in your OP, does have at least one algorithm though
Yes. In two variables, seesay instead of linear form we take in the quadratic form, then does it have any algorithm?
Wow!! getting the hang of it!!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 [itex]x_0[/itex] and [itex]y_0[/itex] so that [itex]ax_0+ by_0= 1[/itex]. Multiply by c to get [itex]a(cx_0)+ b(cy_0)= c[/itex]. [itex]cx_0[/itex] and [itex]cy_0[/itex] 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.
nice step by step solutions.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
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