# Diophantine equation

Graphs of two equations illustrate the difference between an ordinary equation and a Diophantine equation, for which one is interested only in whole-number solutions; this difference is central to Hilbert's 10th problem. The equations in question are *x *^{2} + *y*^{ 2} – 2 = 0 (*left*) and *x*^{ 2} + *y *^{2} – 3 = 0 (*right*); both are represented by circles with their center at the origin, that is, at the point with coordinates *x* = 0, *y* = 0. In the case of *x*^{ 2} + *y*^{ 2} - 2 = 0 the circle has a radius of √2. If the equation is treated as an ordinary equation, there are infinitely many solutions. If, however, it is treated as a Diophantine equation, there are only four solutions: (1) *x* = 1, *y* = 1, (2) *x* = –1, *y* = 1, (3) *x* = 1, *y* = –1, and (4) *x* = –1, *y* = –1. These solutions are represented by dots where the graph crosses the four points with those coordinates on the Cartesian grid. In the case of *x*^{ 2} + *y *^{2} – 3 = 0, the circle has a radius of √3. As an ordinary equation it has an infinite number of solutions; as a Diophantine equation, however, it has none at all.

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.