# Diophantine equation

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, *a*^{2} = *b*^{2} + *c*^{2}, 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), *a ^{n}* =

*b*+

^{n}*c*for

^{n}*n*> 2.

To give a specific example, suppose we want to find integer values for *x* and *y* such that

*x*^{2} = 1620*y*^{2} + 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

*x*^{2} = 1621*y*^{2} + 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}

## References

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.