A Diophantine equation is an equation that has integer coefficients and for which integer solutions are required. Such equations are named after Diophantus. The best known examples are those from Pythagoras's theorem, a2 = b2 + c2, when a, b, and c are all required to be whole numbers – a so-called Pythagorean triplet. Despite their simple appearance Diophantine equations can be fantastically difficult to solve. A notorious example comes from Fermat's last theorem (recently solved), an = bn + cn for n > 2.
To give a specific example, suppose we want to find integer values for x and y such that
x2 = 1620y2 + 1.
A trial and error approach using a computer would quickly find the solution: y = 4, x = 161. However, just a slight change to the equation to make it
x2 = 1621y2 + 1
would leave the trial and error method floundering, even with the resources of the most powerful computers on Earth. The smallest integer solution to this innocent looking formula involves a y-value that is on the order of a thousand trillion trillion trillion trillion trillion trillion!
One of the challenges (the tenth one) that David Hilbert threw down to 20th-century mathematicians in his famous list was to find a general method for solving equations of this type. In 1970, however, the Russian mathematician Yuri Matiyasevich showed that there is no general algorithm for determining whether a particular Diophantine equation is soluble: the problem is undecidable. 1, 2
1. Matijasevic, Yu. V. "Solution of the Tenth Problem of Hilbert." Mat.
Lapok, 21: 83- 87 (1970).
2. Matijasevic, Yu. V. Hilbert's Tenth Problem. Cambridge, Mass.: MIT Press, 1993.