Diophantine Equations

  • Thread starter The legend
  • Start date
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
 
276
0
there is no universal method to solve them :3

simple linear form, in your OP, does have at least one algorithm though
 
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?
 

HallsofIvy

Science Advisor
Homework Helper
41,639
837
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.
 
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.
Wow!! getting the hang of it!!
Thanks a lot!
the example did make it quite clear.
 
84
0
nice step by step solutions.
The method for different types of quadratics is also very very cool:approve:

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

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Hot Threads

Top