1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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