Diophantine equations

Any algebraic equation—such as x³ + x + 1  0—can readily be solved if one allows the variables to have any numerical value. But if one insists that the variables are whole numbers, then the problem is more analogous to the discrete constraints in the main text, and becomes much more difficult. And in fact, even though such so-called Diophantine equations have been studied since well before the time of Diophantus around perhaps 250 AD, only limited results about them are known.

Linear Diophantine equations such as a x  b y + c yield simple repetitive results, as in the pictures below, and can be handled essentially just by knowing ExtendedGCD[a, b].

Even the simplest quadratic Diophantine equations can already show much more complex behavior. The equation x²  a y² has no solution except when a is a perfect square. But the Pell equation x²  a y² + 1 (already studied in antiquity) has infinitely many solutions whenever a is positive and not a perfect square. The smallest solution for x is given by

Numerator[FromContinuedFraction[ContinuedFraction[√a, (If[EvenQ[#], #, 2 #] &)[Length[Last[ContinuedFraction[√a]]]]]]]

This is plotted below; complicated variation and some very large values are seen (with a = 61 for example x  1766319049).

In three variables, the equation x² + y²  z² yields so-called Pythagorean triples {3, 4, 5}, {5, 12, 13}, etc. And even in this case the set of possible solutions for x and y in the pictures below looks fairly complicated—though after removing common factors, they are in fact just given by {x  r² - s², y  2 r s, z  r² + s²}. (See page 1078.)

The pictures below show the possible solutions for x and y in various Diophantine equations. As in other systems based on numbers, nested patterns are not common—though page 1160 shows how they can in principle be achieved with an equation whose solutions satisfy Mod[Binomial[x, y], 2]  1. (The equation (2x + 1) y  z also for example has solutions only when z is not of the form 2^j.)

Many Diophantine equations have at most very sparse solutions. And indeed for example Fermat's Last Theorem states that xⁿ + yⁿ  zⁿ can never be satisfied for n > 2. With four variables one has for example 3³ + 4³ + 5³  6³, 1³ + 6³ + 8³  9³—but with fourth powers the smallest result is 95800⁴ + 217519⁴ + 414560⁴  422481⁴.

(See pages 791 and 1164.)