Diophantine Equation

A Diophantine equation is a polynomial equation with integer coefficients for which integer solutions are sought.

Hilbert's 10th problem asked if an algorithm existed for determining whether an arbitrary Diophantine equation has a solution. Such an algorithm does exist for the solution of first-order Diophantine equations. However, the impossibility of obtaining a general solution was proven by Yuri Matiyasevich in 1970 (Matiyasevich 1970, Davis 1973, Davis and Hersh 1973, Davis 1982, Matiyasevich 1993) by showing that the relation (where is the th Fibonacci number) is Diophantine. More specifically, Matiyasevich showed that there is a polynomial in , , and a number of other variables , , , ... having the property that iff there exist integers , , , ... such that .

Matiyasevich's result filled a crucial gap in previous work by Martin Davis, Hilary Putnam, and Julia Robinson. Subsequent work by Matiyasevich and Robinson proved that even for equations in thirteen variables, no algorithm can determine whether there is a solution in nonnegative integers. Matiyasevich subsequently reduced this bound to nine variables, with a complete proof given by Jones (1982; Sun 2021, p. 283).

Ogilvy and Anderson (1988) give a number of Diophantine equations with known and unknown solutions.

A linear Diophantine equation (in two variables) is an equation of the general form

(1)

where , , and are specified integers and solutions are sought in integers. Such equations can be solved completely, and the first known solution was constructed by Brahmagupta. For relatively prime positive integers , consider the equation

(2)

Now use a variation of the Euclidean algorithm, letting and

			(3)
			(4)
			(5)
			(6)

Starting from the bottom gives

			(7)
			(8)

so

			(9)
			(10)

Continue this procedure all the way back to the top.

Take as an example the equation

(11)

and apply the algorithm above to obtain

(12)

The solution is therefore , .

The backward substitution can be simplified by tracking a pair of signed coefficients. If

			(13)
			(14)
			(15)

then the coefficient pair for the preceding remainders is

(16)

Repeating the above example using this information therefore gives

(17)

and we recover the above solution.

Call the solutions to

(18)

and . If the signs in front of or are negative, then solve the above equation and take the signs of the solutions from the following table:

equation

In fact, the solution to the equation

(19)

is equivalent to finding the continued fraction for , with and relatively prime (Olds 1963). Number the convergents from 1, so , and set , . Then

(20)

so one solution is , , with a general solution

			(21)
			(22)

with an arbitrary integer. The solution in terms of smallest positive integers is given by choosing an appropriate .

Now consider the general first-order equation of the form

(23)

If , every integer pair is a solution when , and there are no solutions otherwise. For , the greatest common divisor can be divided through, yielding

(24)

where , , and . If , then is not an integer and the equation cannot have a solution in integers. A necessary and sufficient condition for the general first-order equation to have solutions in integers is therefore that . If this is the case, then solve

(25)

and multiply the solutions by , since

(26)

D. Wilson has compiled a list of the smallest positive integers whose th powers are sums of the th powers of distinct smaller positive integers. The first few are 3, 5, 6, 15, 12, 25, 40, ...(OEIS A030052):

			(27)
			(28)
			(29)
			(30)
			(31)
			(32)
			(33)
			(34)
			(35)
			(36)