- #1
The legend
- 422
- 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
CRGreathouse said: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 said:there is no universal method to solve them :3
simple linear form, in your OP, does have at least one algorithm though
The legend said:say instead of linear form we take in the quadratic form, then does it have any algorithm?
HallsofIvy said: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.
CRGreathouse said:Yes. In two variables, see
http://www.alpertron.com.ar/QUAD.HTM
The legend said: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 said: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
A Diophantine Equation is a polynomial equation in two or more unknowns where the coefficients and solutions are integers.
Diophantus was an ancient Greek mathematician who lived in the 3rd century. He wrote a series of books called "Arithmetica" which contained solutions to various types of algebraic problems, including what we now call Diophantine Equations. These equations were named after him as a way to honor his contributions to the field of mathematics.
The main difference between Diophantine Equations and regular algebraic equations is that the solutions for Diophantine Equations must be integers, while regular algebraic equations can have solutions that are fractions or decimals. Additionally, Diophantine Equations often involve multiple unknowns and have a finite number of solutions, while regular algebraic equations typically have one or more variables and an infinite number of solutions.
Diophantine Equations have been used in various fields, including cryptography, number theory, and computer science. They have also been used to solve problems related to currency exchange rates, scheduling conflicts, and resource allocation.
Yes, there are several famous unsolved Diophantine Equations, such as Fermat's Last Theorem and the Goldbach Conjecture. These equations have been studied by mathematicians for centuries and continue to inspire new research and discoveries.