Equations that demand whole-number answers, and why no machine can settle them all
Allow fractions and most equations are easy to satisfy. Insist that every answer be a whole number and the problems can become fiendish. These are Diophantine equations, named after a third-century mathematician of Alexandria, and one simple-looking example, Fermat's Last Theorem, held out for more than three hundred years.
Diophantus studied such puzzles and was among the first to write algebra with symbols rather than words. A Diophantine equation is a polynomial with whole-number coefficients whose solutions must also be whole numbers, and there are usually more unknowns than equations. Individual cases have been attacked throughout history, but general theories beyond the linear and quadratic kinds only emerged in the twentieth century.
The linear case is fully understood. An equation of the form ax + by = c has whole-number solutions exactly when the largest number dividing both a and b also divides c, so 6x + 9y = 7 has none, because every combination of 6 and 9 is a multiple of 3. When one solution exists, infinitely many follow by stepping x and y in fixed opposite increments. The Chinese remainder theorem handles an important family of such systems, and larger systems yield to matrix techniques called the Smith and Hermite normal forms; Richard Zippel noted the Hermite form is considerably easier to compute. This machinery underpins integer programming, which seeks the best whole-number solution under constraints.
Higher powers are another matter. For Fermat's equation, which asks for whole numbers whose nth powers add up to another nth power, there are no positive solutions once the exponent exceeds 2. For degrees above three, most known results either rule out solutions entirely or, like Faltings' theorem, show there are only finitely many. Cubic equations have methods that work in nearly every case met in practice, yet no procedure is known to work for all of them.
Hilbert's tenth problem asked for a universal method to decide whether any given Diophantine equation has a whole-number solution. The answer turned out to be that no such algorithm can exist.
Source: Diophantine equation
