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

General solution to diophantine equations

  1. Mar 8, 2007 #1
    Hello, i'm writing an application for a java class that solves the problem where you are given n jugs of arbitrary sizes and have to come up with the steps to reach a certain value.

    I have figured out(read: did research) how to do this in a different way than the original, but it requires math that I don't know how to solve.

    My question is, what is the general method for solving a diophantine equation of the form asub1x+asub2y+...asubnz = something or if you could point me to a paper or article on the subject
  2. jcsd
  3. Mar 8, 2007 #2

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Sorry to disappoint you, but there is no general way to solve a diophantine equation. David Hilbert posed finding a general solution to diophantine equations as his tenth problem at the onset of the 20th century. Martin Davis and Julia Robinson proved that no general solution exists in the middle of the 20th century.
  4. Mar 8, 2007 #3
    Gah, I meant linear diophantine equations, sorry for not specifying.
  5. Mar 14, 2007 #4
    Ignoring a general mathematical solution, I realized that I can modify my brute force algorithm to find the smallest solution(closest to 0) to linear diophantine equations. An interesting application to an otherwise useless problem. I'll link to the library in a few minutes.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook