Diophantine equation

Template:Short description Template:Use dmy dates

Finding all right triangles with integer side-lengths is equivalent to solving the Diophantine equation <math>a^2 + b^2 = c^2.</math>

In mathematics, a Diophantine equation is an equation, typically a polynomial equation in two or more unknowns 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.

ExamplesEdit

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

<math>ax+by = c</math>	This is a linear Diophantine equation, related to Bézout's identity.
<math>w^3 + x^3 = y^3 + z^3</math>	The smallest nontrivial solution in positive integers is Template:Math. It was famously given as an evident property of 1729, a taxicab number (also named Hardy–Ramanujan number) by Ramanujan to Hardy while meeting in 1917.<ref>{{#invoke:citation/CS1\|citation	CitationClass=web }}</ref> There are infinitely many nontrivial solutions.<ref>Template:Citation.</ref>
<math>x^n + y^n = z^n</math>	For Template:Math there are infinitely many solutions Template:Math: the Pythagorean triples. For larger integer values of Template:Mvar, Fermat's Last Theorem (initially claimed in 1637 by Fermat and proved by Andrew Wiles in 1995<ref name=wiles>Template:Cite journal</ref>) states there are no positive integer solutions Template:Math.
<math>x^2 - ny^2 = \pm 1</math>	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.
<math>\frac 4 n = \frac 1 x + \frac 1 y + \frac 1 z</math>	The Erdős–Straus conjecture states that, for every positive integer Template:Mvar ≥ 2, there exists a solution in Template:Mvar, and Template:Mvar, all as positive integers. Although not usually stated in polynomial form, this example is equivalent to the polynomial equation <math>4xyz = n(yz+xz+xy).</math>
<math>x^4 + y^4 + z^4 = w^4</math>	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, Template:Math.<ref>Template:Cite journal</ref><ref>Template:Cite conference</ref>

Template:AnchorLinear Diophantine equationsEdit

One equationEdit

The simplest linear Diophantine equation takes the form <math display=block>ax+by=c,</math> where Template:Mvar, Template:Mvar and Template:Mvar are given integers. The solutions are described by the following theorem:

This Diophantine equation has a solution (where Template:Mvar and Template:Mvar are integers) if and only if Template:Mvar is a multiple of the greatest common divisor of Template:Mvar and Template:Mvar. Moreover, if Template:Math is a solution, then the other solutions have the form Template:Math, where Template:Mvar is an arbitrary integer, and Template:Mvar and Template:Mvar are the quotients of Template:Mvar and Template:Mvar (respectively) by the greatest common divisor of Template:Mvar and Template:Mvar.

Proof: If Template:Mvar is this greatest common divisor, Bézout's identity asserts the existence of integers Template:Mvar and Template:Mvar such that Template:Math. If Template:Mvar is a multiple of Template:Mvar, then Template:Math for some integer Template:Mvar, and Template:Math is a solution. On the other hand, for every pair of integers Template:Mvar and Template:Mvar, the greatest common divisor Template:Mvar of Template:Mvar and Template:Mvar divides Template:Math. Thus, if the equation has a solution, then Template:Mvar must be a multiple of Template:Mvar. If Template:Math and Template:Math, then for every solution Template:Math, we have <math display=block>\begin{align} a(x+kv) + b(y-ku) &= ax+by+k(av-bu) \\ &= ax+by+k(udv-vdu) \\ &= ax+by, \end{align}</math> showing that Template:Math is another solution. Finally, given two solutions such that <math display=block>ax_1 + by_1 = ax_2 + by_2 = c,</math> one deduces that <math display=block>u(x_2 - x_1) + v(y_2 - y_1) = 0.</math> As Template:Mvar and Template:Mvar are coprime, Euclid's lemma shows that Template:Mvar divides Template:Math, and thus that there exists an integer Template:Mvar such that both <math display=block>x_2 - x_1 = kv, \quad y_2 - y_1 = -ku.</math> Therefore, <math display=block>x_2 = x_1 + kv, \quad y_2 = y_1 - ku,</math> which completes the proof.

Chinese remainder theoremEdit

The Chinese remainder theorem describes an important class of linear Diophantine systems of equations: let <math>n_1, \dots, n_k</math> be Template:Mvar pairwise coprime integers greater than one, <math>a_1, \dots, a_k</math> be Template:Mvar arbitrary integers, and Template:Mvar be the product <math>n_1 \cdots n_k.</math> The Chinese remainder theorem asserts that the following linear Diophantine system has exactly one solution <math>(x, x_1, \dots, x_k)</math> such that Template:Math, and that the other solutions are obtained by adding to Template:Mvar a multiple of Template:Mvar: <math display=block>\begin{align} x &= a_1 + n_1\,x_1\\ &\;\;\vdots\\ x &= a_k + n_k\,x_k \end{align}</math>

System of linear Diophantine equationsEdit

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 <math display=block>AX = C,</math> where Template:Mvar is an Template:Math matrix of integers, Template:Mvar is an Template:Math column matrix of unknowns and Template:Mvar is an Template:Math column matrix of integers.

The computation of the Smith normal form of Template:Mvar provides two unimodular matrices (that is matrices that are invertible over the integers and have ±1 as determinant) Template:Mvar and Template:Mvar of respective dimensions Template:Math and Template:Math, such that the matrix <math display=block>B = [b_{i,j}] = UAV</math> is such that Template:Mvar is not zero for Template:Mvar not greater than some integer Template:Mvar, and all the other entries are zero. The system to be solved may thus be rewritten as <math display=block>B (V^{-1}X) = UC.</math> Calling Template:Mvar the entries of Template:Math and Template:Mvar those of Template:Math, this leads to the system <math display=block>\begin{align} & b_{i,i}y_i = d_i, \quad 1 \leq i \leq k \\ & 0y_i = d_i, \quad k < i \leq n. \end{align}</math>

This system is equivalent to the given one in the following sense: A column matrix of integers Template:Mvar is a solution of the given system if and only if Template:Math for some column matrix of integers Template:Mvar such that Template:Math.

It follows that the system has a solution if and only if Template:Mvar divides Template:Mvar for Template:Math and Template:Math for Template:Math. If this condition is fulfilled, the solutions of the given system are <math display=block> V\, \begin{bmatrix} \frac{d_1}{b_{1,1}}\\ \vdots\\ \frac{d_k}{b_{k,k}}\\ h_{k+1}\\ \vdots\\ h_n \end{bmatrix}\,, </math> where Template:Math 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."<ref name="Zippel1993">Template:Cite book</ref>

Integer linear programming amounts to finding some integer solutions (optimal in some sense) 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.<ref>Template:Cite book</ref>

Homogeneous equationsEdit

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 Template:Mvar indeterminates defines a hypersurface in the projective space of dimension Template:Math, 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 (in the case of two indeterminates the problem is equivalent with testing if a rational number is the Template:Mvarth power of another rational number). A witness of the difficulty of the problem is Fermat's Last Theorem (for Template:Math, there is no integer solution of the above equation), 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 (for example Fermat's Last Theorem) or that the number of solutions is finite (for example Falting's theorem).

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.<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref>

Degree twoEdit

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 [[modular arithmetic|modulo Template:Mvar]]. For example, the Diophantine equation

does not have any other solution than the trivial solution Template:Math. In fact, by dividing Template:Mvar, and Template:Mvar 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 Template:Mvar, and Template:Mvar are all even, and are thus not coprime. Thus the only solution is the trivial solution Template:Math. This shows that there is no rational point on a circle of radius <math>\sqrt{3}</math>, 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 interpretationEdit

Let

<math>Q(x_1, \ldots, x_n)=0</math>

be a homogeneous Diophantine equation, where <math>Q(x_1, \ldots, x_n)</math> is a quadratic form (that is, a homogeneous polynomial of degree 2), with integer coefficients. The trivial solution is the solution where all <math>x_i</math> are zero. If <math>(a_1, \ldots, a_n)</math> is a non-trivial integer solution of this equation, then <math>\left(a_1, \ldots, a_n\right)</math> are the homogeneous coordinates of a rational point of the hypersurface defined by Template:Mvar. Conversely, if <math display="inline">\left(\frac {p_1}q, \ldots, \frac {p_n}q \right)</math> are homogeneous coordinates of a rational point of this hypersurface, where <math>q, p_1, \ldots, p_n</math> are integers, then <math>\left(p_1, \ldots, p_n\right)</math> is an integer solution of the Diophantine equation. Moreover, the integer solutions that define a given rational point are all sequences of the form

<math>\left(k\frac{p_1}d, \ldots, k\frac{p_n}d\right),</math>

where Template:Mvar is any integer, and Template:Mvar is the greatest common divisor of the <math>p_i.</math>

It follows that solving the Diophantine equation <math>Q(x_1, \ldots, x_n)=0</math> is completely reduced to finding the rational points of the corresponding projective hypersurface.

ParameterizationEdit

Let now <math>A=\left(a_1, \ldots, a_n\right)</math> be an integer solution of the equation <math>Q(x_1, \ldots, x_n)=0.</math> As Template:Mvar is a polynomial of degree two, a line passing through Template:Mvar crosses the hypersurface at a single other point, which is rational if and only if the line is rational (that is, if the line is defined by rational parameters). This allows parameterizing the hypersurface by the lines passing through Template:Mvar, 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 <math>a_n\ne 0.</math> Then one may pass to the affine case by considering the affine hypersurface defined by

<math>q(x_1,\ldots,x_{n-1})=Q(x_1, \ldots, x_{n-1},1),</math>

which has the rational point

<math>R= (r_1, \ldots, r_{n-1})=\left(\frac{a_1}{a_n}, \ldots, \frac{a_{n-1}}{a_n}\right).</math>

If this rational point is a singular point, that is if all partial derivatives are zero at Template:Mvar, all lines passing through Template:Mvar are contained in the hypersurface, and one has a cone. The change of variables

does not change the rational points, and transforms Template:Mvar into a homogeneous polynomial in Template:Math variables. In this case, the problem may thus be solved by applying the method to an equation with fewer variables.

If the polynomial Template:Mvar is a product of linear polynomials (possibly with non-rational coefficients), 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 Template:Mvar:

<math>\begin{align}

x_2 &= r_2 + t_2(x_1-r_1)\\ &\;\;\vdots\\ x_{n-1} &= r_{n-1} + t_{n-1}(x_1-r_1). \end{align}</math> Substituting this in Template:Mvar, one gets a polynomial of degree two in Template:Math, that is zero for Template:Math. It is thus divisible by Template:Math. The quotient is linear in Template:Math, and may be solved for expressing Template:Math as a quotient of two polynomials of degree at most two in <math>t_2, \ldots, t_{n-1},</math> with integer coefficients:

<math>x_1=\frac{f_1(t_2, \ldots, t_{n-1})}{f_n(t_2, \ldots, t_{n-1})}.</math>

Substituting this in the expressions for <math>x_2, \ldots, x_{n-1},</math> one gets, for Template:Math,

<math>x_i=\frac{f_i(t_2, \ldots, t_{n-1})}{f_n(t_2, \ldots, t_{n-1})},</math>

where <math>f_1, \ldots, f_n</math> are polynomials of degree at most two with integer coefficients.

Then, one can return to the homogeneous case. Let, for Template:Math,

<math>F_i(t_1, \ldots, t_{n-1})=t_1^2 f_i\left(\frac{t_2}{t_1}, \ldots, \frac{t_{n-1}}{t_1} \right),</math>

be the homogenization of <math>f_i.</math> These quadratic polynomials with integer coefficients form a parameterization of the projective hypersurface defined by Template:Mvar:

<math>\begin{align}

x_1&= F_1(t_1, \ldots, t_{n-1})\\ &\;\;\vdots\\ x_n&= F_n(t_1, \ldots, t_{n-1}). \end{align}</math>

A point of the projective hypersurface defined by Template:Mvar is rational if and only if it may be obtained from rational values of <math>t_1, \ldots, t_{n-1}.</math> As <math>F_1, \ldots,F_n</math> are homogeneous polynomials, the point is not changed if all Template:Mvar are multiplied by the same rational number. Thus, one may suppose that <math>t_1, \ldots, t_{n-1}</math> are coprime integers. It follows that the integer solutions of the Diophantine equation are exactly the sequences <math>(x_1, \ldots, x_n)</math> where, for Template:Math,

<math>x_i= k\,\frac{F_i(t_1, \ldots, t_{n-1})}{d},</math>

where Template:Mvar is an integer, <math>t_1, \ldots, t_{n-1}</math> are coprime integers, and Template:Mvar is the greatest common divisor of the Template:Mvar integers <math>F_i(t_1, \ldots, t_{n-1}).</math>

One could hope that the coprimality of the Template:Mvar, could imply that Template:Math. Unfortunately this is not the case, as shown in the next section.

Example of Pythagorean triplesEdit

The equation

is probably the first homogeneous Diophantine equation of degree two that has been studied. Its solutions are the Pythagorean triples. This is also the homogeneous equation of the unit circle. In this section, we show how the above method allows retrieving Euclid's formula for generating Pythagorean triples.

For retrieving exactly Euclid's formula, we start from the solution Template:Math, corresponding to the point Template:Math of the unit circle. A line passing through this point may be parameterized by its slope:

Putting this in the circle equation

one gets

Dividing by Template:Math, results in

which is easy to solve in Template:Mvar:

It follows

Homogenizing as described above one gets all solutions as

<math>\begin{align}

x&=k\,\frac{s^2-t^2}{d}\\ y&=k\,\frac{2st}{d}\\ z&=k\,\frac{s^2+t^2}{d}, \end{align}</math> where Template:Mvar is any integer, Template:Mvar and Template:Mvar are coprime integers, and Template:Mvar is the greatest common divisor of the three numerators. In fact, Template:Math if Template:Mvar and Template:Mvar are both odd, and Template:Math if one is odd and the other is even.

The primitive triples are the solutions where Template:Math and Template:Math.

This description of the solutions differs slightly from Euclid's formula because Euclid's formula considers only the solutions such that Template:Mvar, and Template:Mvar are all positive, and does not distinguish between two triples that differ by the exchange of Template:Mvar and Template:Mvar,

Diophantine analysisEdit

Typical questionsEdit

The questions asked in Diophantine analysis include:

Are there any solutions?
Are there any solutions beyond some that are easily found by inspection?
Are there finitely or infinitely many solutions?
Can all solutions be found in theory?
Can one in practice compute a full list of solutions?

These traditional problems often lay unsolved for centuries, and mathematicians gradually came to understand their depth (in some cases), rather than treat them as puzzles.

Typical problemEdit

The given information is that a father's age is 1 less than twice that of his son, and that the digits Template:Mvar making up the father's age are reversed in the son's age (i.e. Template:Mvar). This leads to the equation Template:Math, thus Template:Math. Inspection gives the result Template:Math, Template:Math, and thus Template:Mvar equals 73 years and Template:Mvar equals 37 years. One may easily show that there is not any other solution with Template:Mvar and Template:Mvar positive integers less than 10.

Many well known puzzles in the field of recreational mathematics lead to diophantine equations. Examples include the cannonball problem, Archimedes's cattle problem and the monkey and the coconuts.

17th and 18th centuriesEdit

In 1637, Pierre de Fermat scribbled on the margin of his copy of Arithmetica: "It is impossible to separate a cube into two cubes, or a fourth power into two fourth powers, or in general, any power higher than the second into two like powers." Stated in more modern language, "The equation Template:Math has no solutions for any Template:Mvar higher than 2." Following this, he wrote: "I have discovered a truly marvelous proof of this proposition, which this margin is too narrow to contain." Such a proof eluded mathematicians for centuries, however, and as such his statement became famous as Fermat's Last Theorem. It was not until 1995 that it was proven by the British mathematician Andrew Wiles.

In 1657, Fermat attempted to solve the Diophantine equation Template:Math (solved by Brahmagupta over 1000 years earlier). The equation was eventually solved by Euler in the early 18th century, who also solved a number of other Diophantine equations. The smallest solution of this equation in positive integers is Template:Math, Template:Math (see Chakravala method).

Hilbert's tenth problemEdit

Template:Main article In 1900, David Hilbert proposed the solvability of all Diophantine equations as the tenth of his fundamental problems. In 1970, Yuri Matiyasevich solved it negatively, building on work of Julia Robinson, Martin Davis, and Hilary Putnam to prove that a general algorithm for solving all Diophantine equations cannot exist.

Diophantine geometryEdit

Diophantine geometry, is the application of techniques from algebraic geometry which considers equations that also have a geometric meaning. The central idea of Diophantine geometry is that of a rational point, namely a solution to a polynomial equation or a system of polynomial equations, which is a vector in a prescribed field Template:Mvar, when Template:Mvar is not algebraically closed.

Modern researchEdit

The oldest general method for solving a Diophantine equationTemplate:Mdashor for proving that there is no solutionTemplate:Mdash is the method of infinite descent, which was introduced by Pierre de Fermat. Another general method is the Hasse principle that uses modular arithmetic modulo all prime numbers for finding the solutions. Despite many improvements these methods cannot solve most Diophantine equations.

The difficulty of solving Diophantine equations is illustrated by Hilbert's tenth problem, which was set in 1900 by David Hilbert; it was to find an algorithm to determine whether a given polynomial Diophantine equation with integer coefficients has an integer solution. Matiyasevich's theorem implies that such an algorithm cannot exist.

During the 20th century, a new approach has been deeply explored, consisting of using algebraic geometry. In fact, a Diophantine equation can be viewed as the equation of an hypersurface, and the solutions of the equation are the points of the hypersurface that have integer coordinates.

This approach led eventually to the proof by Andrew Wiles in 1994 of Fermat's Last Theorem, stated without proof around 1637. This is another illustration of the difficulty of solving Diophantine equations.

Infinite Diophantine equationsEdit

An example of an infinite Diophantine equation is: <math display=block>n = a^2 + 2b^2 + 3c^2 + 4d^2 + 5e^2 + \cdots,</math> which can be expressed as "How many ways can a given integer Template:Mvar be written as the sum of a square plus twice a square plus thrice a square and so on?" The number of ways this can be done for each Template:Mvar forms an integer sequence. Infinite Diophantine equations are related to theta functions and infinite dimensional lattices. This equation always has a solution for any positive Template:Mvar.<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref> Compare this to: <math display=block>n = a^2 + 4b^2 + 9c^2 + 16d^2 + 25e^2 + \cdots,</math> which does not always have a solution for positive Template:Mvar.

Exponential Diophantine equationsEdit

If a Diophantine equation has as an additional variable or variables occurring as exponents, it is an exponential Diophantine equation. Examples include:

the Ramanujan–Nagell equation, Template:Math
the equation of the Fermat–Catalan conjecture and Beal's conjecture, Template:Math with inequality restrictions on the exponents
the Erdős–Moser equation, Template:Math

A general theory for such equations is not available; particular cases such as Catalan's conjecture and Fermat's Last Theorem have been tackled. However, the majority are solved via ad-hoc methods such as Størmer's theorem or even trial and error.

NotesEdit

Template:Reflist

ReferencesEdit

External linksEdit

Diophantine Equation. From MathWorld at Wolfram Research.
Template:Springer
Dario Alpern's Online Calculator. Retrieved 18 March 2009

Template:Ancient Greek mathematics

Template:Authority control

Diophantine equation

Contents

ExamplesEdit

Template:AnchorLinear Diophantine equationsEdit

One equationEdit

Chinese remainder theoremEdit

System of linear Diophantine equationsEdit

Homogeneous equationsEdit

Degree twoEdit

Geometric interpretationEdit

ParameterizationEdit

Example of Pythagorean triplesEdit

Diophantine analysisEdit

Typical questionsEdit

Typical problemEdit

17th and 18th centuriesEdit

Hilbert's tenth problemEdit

Diophantine geometryEdit

Modern researchEdit

Infinite Diophantine equationsEdit

Exponential Diophantine equationsEdit

See alsoEdit

NotesEdit

ReferencesEdit

Further readingEdit

External linksEdit