Diophantine equation

In mathematics, a Diophantine equation is a polynomial equation with integer coefficients, for which only integer solutions are of interest. A linear Diophantine equation equates the sum of two or more unknowns, with coefficients, to a constant. An exponential Diophantine equation is one in which unknowns can appear in exponents.
Diophantine problems have fewer equations than unknowns and involve finding integers that solve all equations simultaneously. Because such systems of equations define algebraic curves, algebraic surfaces, or, more generally, algebraic sets, their study is a part of algebraic geometry that is called Diophantine geometry.
The word Diophantine refers to the Hellenistic mathematician of the 3rd century, Diophantus of Alexandria, who made a study of such equations and was one of the first mathematicians to introduce symbolism into algebra. The mathematical study of Diophantine problems that Diophantus initiated is now called Diophantine analysis.
While individual equations present a kind of puzzle and have been considered throughout history, the formulation of general theories of Diophantine equations, beyond the case of linear and quadratic equations, was an achievement of the twentieth century.

Examples

In the following Diophantine equations,, and are the unknowns and the other letters are given constants:

	This is a linear Diophantine equation, related to Bézout's identity.
	The smallest nontrivial solution in positive integers is. It was famously given as an evident property of 1729, a taxicab number by Ramanujan to Hardy while meeting in 1917. There are infinitely many nontrivial solutions.
	For there are infinitely many solutions : the Pythagorean triples. For larger integer values of, Fermat's Last Theorem states there are no positive integer solutions.
	This is Pell's equation, which is named after the English mathematician John Pell. It was studied by Brahmagupta in the 7th century, as well as by Fermat in the 17th century.
	The Erdős–Straus conjecture states that, for every positive integer ≥ 2, there exists a solution in, and, all as positive integers. Although not usually stated in polynomial form, this example is equivalent to the polynomial equation
	Conjectured incorrectly by Euler to have no nontrivial solutions. Proved by Elkies to have infinitely many nontrivial solutions, with a computer search by Frye determining the smallest nontrivial solution,.

Linear Diophantine equations

One equation

The simplest linear Diophantine equation takes the form
where, and are given integers. The solutions are described by the following theorem:
Proof: If is this greatest common divisor, Bézout's identity asserts the existence of integers and such that. If is a multiple of, then for some integer, and is a solution. On the other hand, for every pair of integers and, the greatest common divisor of and divides. Thus, if the equation has a solution, then must be a multiple of. If and, then for every solution, we have
showing that is another solution. Finally, given two solutions such that
one deduces that
As and are coprime, Euclid's lemma shows that divides, and thus that there exists an integer such that both
Therefore,
which completes the proof.

Chinese remainder theorem

The Chinese remainder theorem describes an important class of linear Diophantine systems of equations: let be pairwise coprime integers greater than one, be arbitrary integers, and be the product The Chinese remainder theorem asserts that the following linear Diophantine system has exactly one solution such that, and that the other solutions are obtained by adding to a multiple of :

System of linear Diophantine equations

More generally, every system of linear Diophantine equations may be solved by computing the Smith normal form of its matrix, in a way that is similar to the use of the reduced row echelon form to solve a system of linear equations over a field. Using matrix notation every system of linear Diophantine equations may be written
where is an matrix of integers, is an column matrix of unknowns and is an column matrix of integers.
The computation of the Smith normal form of provides two unimodular matrices and of respective dimensions and, such that the matrix
is such that is not zero for not greater than some integer, and all the other entries are zero. The system to be solved may thus be rewritten as
Calling the entries of and those of, this leads to the system
This system is equivalent to the given one in the following sense: A column matrix of integers is a solution of the given system if and only if for some column matrix of integers such that.
It follows that the system has a solution if and only if divides for and for. If this condition is fulfilled, the solutions of the given system are
where are arbitrary integers.
Hermite normal form may also be used for solving systems of linear Diophantine equations. However, Hermite normal form does not directly provide the solutions; to get the solutions from the Hermite normal form, one has to successively solve several linear equations. Nevertheless, Richard Zippel wrote that the Smith normal form "is somewhat more than is actually needed to solve linear diophantine equations. Instead of reducing the equation to diagonal form, we only need to make it triangular, which is called the Hermite normal form. The Hermite normal form is substantially easier to compute than the Smith normal form."
Integer linear programming amounts to finding some integer solutions of linear systems that include also inequations. Thus systems of linear Diophantine equations are basic in this context, and textbooks on integer programming usually have a treatment of systems of linear Diophantine equations.

Homogeneous equations

A homogeneous Diophantine equation is a Diophantine equation that is defined by a homogeneous polynomial. A typical such equation is the equation of Fermat's Last Theorem
As a homogeneous polynomial in indeterminates defines a hypersurface in the projective space of dimension, solving a homogeneous Diophantine equation is the same as finding the rational points of a projective hypersurface.
Solving a homogeneous Diophantine equation is generally a very difficult problem, even in the simplest non-trivial case of three indeterminates. A witness of the difficulty of the problem is Fermat's Last Theorem, which needed more than three centuries of mathematicians' efforts before being solved.
For degrees higher than three, most known results are theorems asserting that there are no solutions or that the number of solutions is finite.
For the degree three, there are general solving methods, which work on almost all equations that are encountered in practice, but no algorithm is known that works for every cubic equation.

Degree two

Homogeneous Diophantine equations of degree two are easier to solve. The standard solving method proceeds in two steps. One has first to find one solution, or to prove that there is no solution. When a solution has been found, all solutions are then deduced.
For proving that there is no solution, one may reduce the equation modulo. For example, the Diophantine equation
does not have any other solution than the trivial solution. In fact, by dividing, and by their greatest common divisor, one may suppose that they are coprime. The squares modulo 4 are congruent to 0 and 1. Thus the left-hand side of the equation is congruent to 0, 1, or 2, and the right-hand side is congruent to 0 or 3. Thus the equality may be obtained only if, and are all even, and are thus not coprime. Thus the only solution is the trivial solution. This shows that there is no rational point on a circle of radius, centered at the origin.
More generally, the Hasse principle allows deciding whether a homogeneous Diophantine equation of degree two has an integer solution, and computing a solution if there exist.
If a non-trivial integer solution is known, one may produce all other solutions in the following way.

Geometric interpretation

Let
be a homogeneous Diophantine equation, where is a quadratic form, with integer coefficients. The trivial solution is the solution where all are zero. If is a non-trivial integer solution of this equation, then are the homogeneous coordinates of a rational point of the hypersurface defined by. Conversely, if are homogeneous coordinates of a rational point of this hypersurface, where are integers, then is an integer solution of the Diophantine equation. Moreover, the integer solutions that define a given rational point are all sequences of the form
where is any integer, and is the greatest common divisor of the
It follows that solving the Diophantine equation is completely reduced to finding the rational points of the corresponding projective hypersurface.

Parameterization

Let now be an integer solution of the equation As is a polynomial of degree two, a line passing through crosses the hypersurface at a single other point, which is rational if and only if the line is rational. This allows parameterizing the hypersurface by the lines passing through, and the rational points are those that are obtained from rational lines, that is, those that correspond to rational values of the parameters.
More precisely, one may proceed as follows.
By permuting the indices, one may suppose, without loss of generality that Then one may pass to the affine case by considering the affine hypersurface defined by
which has the rational point
If this rational point is a singular point, that is if all partial derivatives are zero at, all lines passing through are contained in the hypersurface, and one has a cone. The change of variables
does not change the rational points, and transforms into a homogeneous polynomial in variables. In this case, the problem may thus be solved by applying the method to an equation with fewer variables.
If the polynomial is a product of linear polynomials, then it defines two hyperplanes. The intersection of these hyperplanes is a rational flat, and contains rational singular points. This case is thus a special instance of the preceding case.
In the general case, consider the parametric equation of a line passing through :
Substituting this in, one gets a polynomial of degree two in, that is zero for. It is thus divisible by. The quotient is linear in, and may be solved for expressing as a quotient of two polynomials of degree at most two in with integer coefficients:
Substituting this in the expressions for one gets, for,
where are polynomials of degree at most two with integer coefficients.
Then, one can return to the homogeneous case. Let, for,
be the homogenization of These quadratic polynomials with integer coefficients form a parameterization of the projective hypersurface defined by :
A point of the projective hypersurface defined by is rational if and only if it may be obtained from rational values of As are homogeneous polynomials, the point is not changed if all are multiplied by the same rational number. Thus, one may suppose that are coprime integers. It follows that the integer solutions of the Diophantine equation are exactly the sequences where, for,
where is an integer, are coprime integers, and is the greatest common divisor of the integers
One could hope that the coprimality of the, could imply that. Unfortunately this is not the case, as shown in the next section.