In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, a Diophantine equation is an
equation
In mathematics, an equation is a formula that expresses the equality of two expressions, by connecting them with the equals sign . The word ''equation'' and its cognates in other languages may have subtly different meanings; for example, in F ...
, typically a
polynomial equation in two or more
unknown
Unknown or The Unknown may refer to:
Film
* ''The Unknown'' (1915 comedy film), a silent boxing film
* ''The Unknown'' (1915 drama film)
* ''The Unknown'' (1927 film), a silent horror film starring Lon Chaney
* ''The Unknown'' (1936 film), a ...
s with
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
coefficients, such that the only
solutions of interest are the
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
ones. A linear Diophantine equation equates to a constant the sum of two or more
monomials, each of
degree one. 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 simultaneously all equations. As such
systems of equations define
algebraic curves,
algebraic surface
In mathematics, an algebraic surface is an algebraic variety of dimension two. In the case of geometry over the field of complex numbers, an algebraic surface has complex dimension two (as a complex manifold, when it is non-singular) and so of di ...
s, or, more generally,
algebraic sets, their study is a part of
algebraic geometry
Algebraic geometry is a branch of mathematics, classically studying zeros of multivariate polynomials. Modern algebraic geometry is based on the use of abstract algebraic techniques, mainly from commutative algebra, for solving geometrical ...
that is called ''
Diophantine geometry''.
The word ''Diophantine'' refers to the
Hellenistic mathematician of the 3rd century,
Diophantus
Diophantus of Alexandria ( grc, Διόφαντος ὁ Ἀλεξανδρεύς; born probably sometime between AD 200 and 214; died around the age of 84, probably sometime between AD 284 and 298) was an Alexandrian mathematician, who was the aut ...
of
Alexandria
Alexandria ( or ; ar, ٱلْإِسْكَنْدَرِيَّةُ ; grc-gre, Αλεξάνδρεια, Alexándria) is the second largest city in Egypt, and the largest city on the Mediterranean coast. Founded in by Alexander the Great, Alexandri ...
, who made a study of such equations and was one of the first mathematicians to introduce
symbolism into
algebra
Algebra () is one of the broad areas of mathematics. Roughly speaking, algebra is the study of mathematical symbols and the rules for manipulating these symbols in formulas; it is a unifying thread of almost all of mathematics.
Elementary ...
. 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:
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:
:''This Diophantine equation has a solution'' (where and are integers) ''if and only if'' ''is a multiple of the
greatest common divisor of'' ''and'' . ''Moreover, if'' ''is a solution, then the other solutions have the form'' , ''where'' ''is an arbitrary integer, and'' ''and'' ''are the quotients of'' ''and'' ''(respectively) by the greatest common divisor of'' ''and'' .
Proof: If is this greatest common divisor,
Bézout's identity
In mathematics, Bézout's identity (also called Bézout's lemma), named after Étienne Bézout, is the following theorem:
Here the greatest common divisor of and is taken to be . The integers and are called Bézout coefficients for ; they ...
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 and . Therefore, and , which completes the proof.
Chinese remainder theorem
The
Chinese remainder theorem
In mathematics, the Chinese remainder theorem states that if one knows the remainders of the Euclidean division of an integer ''n'' by several integers, then one can determine uniquely the remainder of the division of ''n'' by the product of the ...
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
In linear algebra, a matrix is in echelon form if it has the shape resulting from a Gaussian elimination.
A matrix being in row echelon form means that Gaussian elimination has operated on the rows, and
column echelon form means that Gaussian e ...
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
In linear algebra, a column vector with m elements is an m \times 1 matrix consisting of a single column of m entries, for example,
\boldsymbol = \begin x_1 \\ x_2 \\ \vdots \\ x_m \end.
Similarly, a row vector is a 1 \times n matrix for some n, c ...
of unknowns and is an column matrix of integers.
The computation of the Smith normal form of provides two
unimodular matrices (that is matrices that are invertible over the integers and have ±1 as determinant) 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
: for ,
: for .
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 (optimal in some sense) of linear systems that include also
inequation
In mathematics, an inequation is a statement that an inequality holds between two values. It is usually written in the form of a pair of expressions denoting the values in question, with a relational sign between them indicating the specific in ...
s. 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
In mathematics, a homogeneous polynomial, sometimes called quantic in older texts, is a polynomial whose nonzero terms all have the same degree. For example, x^5 + 2 x^3 y^2 + 9 x y^4 is a homogeneous polynomial of degree 5, in two variables; ...
. 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 (in the case of two indeterminates the problem is equivalent with testing if a
rational number
In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ). The set of all ra ...
is the th power of another rational number). A witness of the difficulty of the problem is Fermat's Last Theorem (for , 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
In arithmetic geometry, the Mordell conjecture is the conjecture made by Louis Mordell that a curve of genus greater than 1 over the field Q of rational numbers has only finitely many rational points. In 1983 it was proved by Gerd Faltings, and ...
).
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
A circle is a shape consisting of all points in a plane that are at a given distance from a given point, the centre. Equivalently, it is the curve traced out by a point that moves in a plane so that its distance from a given point is cons ...
of radius
centered at the origin.
More generally, the
Hasse principle In mathematics, Helmut Hasse's local–global principle, also known as the Hasse principle, is the idea that one can find an diophantine equation, integer solution to an equation by using the Chinese remainder theorem to piece together solutions mod ...
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
In mathematics, a quadratic form is a polynomial with terms all of degree two ("form" is another name for a homogeneous polynomial). For example,
:4x^2 + 2xy - 3y^2
is a quadratic form in the variables and . The coefficients usually belong to ...
(that is, a homogeneous polynomial of degree 2), 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
In mathematics, homogeneous coordinates or projective coordinates, introduced by August Ferdinand Möbius in his 1827 work , are a system of coordinates used in projective geometry, just as Cartesian coordinates are used in Euclidean geometr ...
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 (that is, if the line is defined by rational parameters). This allows parameterizing the hypersurface by the lines passing through , and the rational points are the 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
Singularity or singular point may refer to:
Science, technology, and mathematics Mathematics
* Mathematical singularity, a point at which a given mathematical object is not defined or not "well-behaved", for example infinite or not differentiab ...
, that is if all
partial derivative
In mathematics, a partial derivative of a function of several variables is its derivative with respect to one of those variables, with the others held constant (as opposed to the total derivative, in which all variables are allowed to vary). Pa ...
s 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 (possibly with non-rational coefficients), then it defines two
hyperplane
In geometry, a hyperplane is a subspace whose dimension is one less than that of its '' ambient space''. For example, if a space is 3-dimensional then its hyperplanes are the 2-dimensional planes, while if the space is 2-dimensional, its hyper ...
s. 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, let 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
Homogeneity is a sameness of constituent structure.
Homogeneity, homogeneous, or homogenization may also refer to:
In mathematics
*Transcendental law of homogeneity of Leibniz
* Homogeneous space for a Lie group G, or more general transformatio ...
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.
Example of Pythagorean triples
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
A Pythagorean triple consists of three positive integers , , and , such that . Such a triple is commonly written , and a well-known example is . If is a Pythagorean triple, then so is for any positive integer . A primitive Pythagorean triple is ...
for generating Pythagorean triples.
For retrieving exactly Euclid's formula, we start from the solution , corresponding to the point 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 , results in
:
which is easy to solve in :
:
It follows
:
Homogenizing as described above one gets all solutions as
:
where is any integer, and are coprime integers, and is the greatest common divisor of the three numerators. In fact, if and are both odd, and if one is odd and the other is even.
The ''primitive triples'' are the solutions where and .
This description of the solutions differs slightly from Euclid's formula because Euclid's formula considers only the solutions such that and are all positive, and does not distinguish between two triples that differ by the exchange of and ,
Diophantine analysis
Typical questions
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 problem
The given information is that a father's age is 1 less than twice that of his son, and that the digits making up the father's age are reversed in the son's age (i.e. ). This leads to the equation , thus . Inspection gives the result , , and thus equals 73 years and equals 37 years. One may easily show that there is not any other solution with and 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
The monkey and the coconuts is a mathematical puzzle in the field of Diophantine analysis that originated in a magazine fictional short story involving five sailors and a monkey on a desert island who divide up a pile of coconuts; the problem is ...
.
17th and 18th centuries
In 1637,
Pierre de Fermat
Pierre de Fermat (; between 31 October and 6 December 1607 – 12 January 1665) was a French mathematician who is given credit for early developments that led to infinitesimal calculus, including his technique of adequality. In particular, he ...
scribbled on the margin of his copy of ''
Arithmetica
''Arithmetica'' ( grc-gre, Ἀριθμητικά) is an Ancient Greek text on mathematics written by the mathematician Diophantus () in the 3rd century AD. It is a collection of 130 algebraic problems giving numerical solutions of determinate ...
'': "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 has no solutions for any 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 (solved by
Brahmagupta
Brahmagupta ( – ) was an Indian mathematician and astronomer. He is the author of two early works on mathematics and astronomy: the '' Brāhmasphuṭasiddhānta'' (BSS, "correctly established doctrine of Brahma", dated 628), a theoretical tr ...
over 1000 years earlier). The equation was eventually solved by
Euler
Leonhard Euler ( , ; 15 April 170718 September 1783) was a Swiss mathematician, physicist, astronomer, geographer, logician and engineer who founded the studies of graph theory and topology and made pioneering and influential discoveries in ...
in the early 18th century, who also solved a number of other Diophantine equations. The smallest solution of this equation in positive integers is , (see
Chakravala method).
Hilbert's tenth problem
In 1900,
David Hilbert
David Hilbert (; ; 23 January 1862 – 14 February 1943) was a German mathematician, one of the most influential mathematicians of the 19th and early 20th centuries. Hilbert discovered and developed a broad range of fundamental ideas in many ...
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
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
for solving all Diophantine equations
cannot exist.
Diophantine geometry
Diophantine geometry, which is the application of techniques from
algebraic geometry
Algebraic geometry is a branch of mathematics, classically studying zeros of multivariate polynomials. Modern algebraic geometry is based on the use of abstract algebraic techniques, mainly from commutative algebra, for solving geometrical ...
in this field, has continued to grow as a result; since treating arbitrary equations is a dead end, attention turns to 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 , when is ''not''
algebraically closed.
Modern research
One of the few general approaches is through the
Hasse principle In mathematics, Helmut Hasse's local–global principle, also known as the Hasse principle, is the idea that one can find an diophantine equation, integer solution to an equation by using the Chinese remainder theorem to piece together solutions mod ...
.
Infinite descent In mathematics, a proof by infinite descent, also known as Fermat's method of descent, is a particular kind of proof by contradiction used to show that a statement cannot possibly hold for any number, by showing that if the statement were to hold f ...
is the traditional method, and has been pushed a long way.
The depth of the study of general Diophantine equations is shown by the characterisation of
Diophantine sets as equivalently described as
recursively enumerable. In other words, the general problem of Diophantine analysis is blessed or cursed with universality, and in any case is not something that will be solved except by re-expressing it in other terms.
The field of
Diophantine approximation deals with the cases of ''Diophantine inequalities''. Here variables are still supposed to be integral, but some coefficients may be irrational numbers, and the equality sign is replaced by upper and lower bounds.
The single most celebrated question in the field, the
conjecture
In mathematics, a conjecture is a conclusion or a proposition that is proffered on a tentative basis without proof. Some conjectures, such as the Riemann hypothesis (still a conjecture) or Fermat's Last Theorem (a conjecture until proven in ...
known as
Fermat's Last Theorem, was
solved by Andrew Wiles,
[ using tools from algebraic geometry developed during the last century rather than within number theory where the conjecture was originally formulated. Other major results, such as Faltings's theorem, have disposed of old conjectures.
]
Infinite Diophantine equations
An example of an infinite diophantine equation is:
:, which can be expressed as "How many ways can a given integer 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 forms an integer sequence. Infinite Diophantine equations are related to theta functions
In mathematics, theta functions are special functions of several complex variables. They show up in many topics, including Abelian varieties, moduli spaces, quadratic forms, and solitons. As Grassmann algebras, they appear in quantum field ...
and infinite dimensional lattices. This equation always has a solution for any positive . Compare this to:
:,
which does not always have a solution for positive .
Exponential Diophantine equations
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 In mathematics, in the field of number theory, the Ramanujan–Nagell equation is an equation between a square number and a number that is seven less than a power of two. It is an example of an exponential Diophantine equation, an equation to ...
, , and the equation of the Fermat–Catalan conjecture and Beal's conjecture
The Beal conjecture is the following conjecture in number theory:
:If
:: A^x +B^y = C^z,
:where ''A'', ''B'', ''C'', ''x'', ''y'', and ''z'' are positive integers with ''x'', ''y'', ''z'' ≥ 3, then ''A'', ''B'', and ''C'' have a common prime ...
, with inequality restrictions on the exponents. A general theory for such equations is not available; particular cases such as Catalan's conjecture have been tackled. However, the majority are solved via ad hoc methods such as Størmer's theorem
In number theory, Størmer's theorem, named after Carl Størmer, gives a finite bound on the number of consecutive pairs of smooth numbers that exist, for a given degree of smoothness, and provides a method for finding all such pairs using Pell equ ...
or even trial and error.
See also
* Kuṭṭaka, Aryabhata's algorithm for solving linear Diophantine equations in two unknowns
Notes
References
*
*
*
*
*
Further reading
*Bashmakova, Izabella G. "Diophante et Fermat", ''Revue d'Histoire des Sciences'' 19 (1966), pp. 289–306
*Bashmakova, Izabella G. '' Diophantus and Diophantine Equations''. Moscow: Nauka 1972 n Russian German translation: ''Diophant und diophantische Gleichungen''. Birkhauser, Basel/ Stuttgart, 1974. English translation: ''Diophantus and Diophantine Equations''. Translated by Abe Shenitzer with the editorial assistance of Hardy Grant and updated by Joseph Silverman. The Dolciani Mathematical Expositions, 20. Mathematical Association of America, Washington, DC. 1997.
*Bashmakova, Izabella G.
Arithmetic of Algebraic Curves from Diophantus to Poincaré"
''Historia Mathematica'' 8 (1981), 393–416.
*Bashmakova, Izabella G., Slavutin, E. I. ''History of Diophantine Analysis from Diophantus to Fermat''. Moscow: Nauka 1984 n Russian
*Bashmakova, Izabella G. "Diophantine Equations and the Evolution of Algebra", ''American Mathematical Society Translations'' 147 (2), 1990, pp. 85–100. Translated by A. Shenitzer and H. Grant.
*
*Rashed, Roshdi, Houzel, Christian. ''Les Arithmétiques de Diophante : Lecture historique et mathématique'', Berlin, New York : Walter de Gruyter, 2013.
*Rashed, Roshdi, ''Histoire de l'analyse diophantienne classique : D'Abū Kāmil à Fermat'', Berlin, New York : Walter de Gruyter.
External links
Diophantine Equation
From MathWorld at Wolfram Research.
*
Dario Alpern's Online Calculator
Retrieved 18 March 2009
{{DEFAULTSORT:Diophantine Equation
*