Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Diophantine Equations

  1. Sep 29, 2010 #1
    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
     
  2. jcsd
  3. Sep 29, 2010 #2

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

  4. Sep 29, 2010 #3
    there is no universal method to solve them :3

    simple linear form, in your OP, does have at least one algorithm though
     
  5. Sep 29, 2010 #4
  6. Sep 29, 2010 #5
    say instead of linear form we take in the quadratic form, then does it have any algorithm?
     
  7. Sep 29, 2010 #6

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

  8. Sep 29, 2010 #7

    HallsofIvy

    User Avatar
    Science Advisor

    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.
     
  9. Sep 29, 2010 #8
    Wow!! getting the hang of it!!
    Thanks a lot!
    the example did make it quite clear.
     
  10. Sep 29, 2010 #9
  11. Sep 30, 2010 #10

    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
     
  12. Sep 30, 2010 #11

    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.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook