Chapter 12: The Principle of Computational Equivalence

Section 9: Implications for Mathematics and Its Foundations

Properties [of Diophantine equations]

(All variables are assumed positive.)

2x+3y==a. There are Ceiling[a/2] + Ceiling[2 a/3] - (a+1) solutions, the one with smallest x being {Mod[2*a+2, 3]+1, 2*Floor[(2a+2)/3]-(a+2)}. Linear equations like this were already studied in antiquity. (Compare page 915.)

x2==y2+a. Writing a in terms of distinct factors as r s, {r+s, r-s}/2 gives a solution if it yields integers—which happens when Abs[a] > 4 and Mod[a,4]!=2.

x2==a y2+1 (Pell equation). As discussed on page 944, whenever a is not a perfect square, there are always an infinite number of solutions given in terms of ContinuedFraction[Sqrt[a]]. Note that even when the smallest solution is not very large, subsequent solutions can rapidly get large. Thus for example when a=13, the second solution is already {842401, 233640}.

x2==y3+a (Mordell equation). First studied in the 1600s, a complete theory of this so-called elliptic curve equation was only developed in the late 1900s—using fairly sophisticated algebraic number theory. The picture below shows as a function of a the minimum x that solves the equation. For a=68, the only solution is x=1874; for a=1090, it is x=149651610621. The density of cases with solutions gradually thins out as a increases (for 0<a<=10000 there are 2468 such cases). There are always only a finite number of solutions (for 0 <a<=10000 the maximum is 12, achieved for a=8900).

x2==a y3+1. Also an elliptic curve equation.

x3==y4+x y + a. For most values of a (including specifically a=1) the continuous version of this equation defines a surface of genus 3, so there are at most a finite number of integer solutions. (An equation of degree d generically defines a surface of genus (d-1)(d-2)/2.) Note that x3 ==y4+a is equivalent to x3==z2+a by a simple substitution.

x2==y5+a y +3. The second smallest solution to x2 == y5 + 5*y + 3 is {45531, 73}. As for the equations above, there are always at most a finite number of integer solutions.

x3+y3==z2+a. For the homogenous case a=0 the complete solution was found by Leonhard Euler in 1756.

x3+y3==z3+a. No solutions exist when a=9n±4; for a=n3 or 2n3 infinite families of solutions are known. Particularly in its less strict form x3+y3+z3==a with x, y, z positive or negative the equation was mentioned in the 1800s and again in the mid-1900s; computer searches for solutions were begun in the 1960s, and by the mid-1990s solutions such as {283059965, 2218888517, 2220422932} for the case a= -30 had been found. Any solution to the difficult case x3+y3==z3-3 must have Mod[x,9]==Mod[y,9]==Mod[z,9]. (Note that x2+y2+z2==a always has solutions except when a=4s (8n+7), as mentioned on page 135.)

From Stephen Wolfram: A New Kind of Science [citation]