Diophantine equation
Encyclopedia
In mathematics
, a Diophantine equation is an indeterminate
polynomial
equation
that allows the variable
s to be integer
s only. Diophantine problems have fewer equations than unknown variables and involve finding integers that work correctly for all equations. In more technical language, they define an algebraic curve
, algebraic surface
, or more general object, and ask about the lattice points on it.
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 Diophantus initiated is now called "Diophantine analysis". A linear Diophantine equation is an equation between two sums of monomials of degree zero or one.
While individual equations present a kind of puzzle and have been considered throughout history, the formulation of general theories of Diophantine equations (beyond the theory of quadratic form
s) was an achievement of the twentieth century.
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.
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 an + bn = cn has no solutions for any n higher than two." And then he wrote, intriguingly: "I have discovered a truly marvelous proof of this, which, however, the margin is not large enough to contain." Such a proof eluded mathematicians for centuries, however. As an unproven conjecture
that eluded brilliant mathematicians' attempts to either prove it or disprove it for generations, his statement became famous as Fermat's Last Theorem
. It wasn't until 1994 that it was proven by the British
mathematician Andrew Wiles
.
In 1657, Fermat attempted the Diophantine equation 61x2 + 1 = y2 (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.
proposed the solvability of all Diophantine problems as the tenth
of his celebrated problems
. In 1970, a novel result in mathematical logic
known as Matiyasevich's theorem settled the problem negatively: in general Diophantine problems are unsolvable.
Diophantine geometry, which is the application of techniques from algebraic geometry
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 system of simultaneous equations
, which is a vector in a prescribed field
K, when K is not algebraically closed.
. Infinite descent
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 set
s 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 most celebrated single question in the field, the conjecture
known as Fermat's Last Theorem
, was solved by Andrew Wiles
but 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' theorem
, have disposed of old conjectures.
which can be expressed as "How many ways can a given integer (N) 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 N 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 N. Compare this to:
which doesn't always have a solution for positive N.
of a and b then this is Bézout's identity, and the equation has an infinite number of solutions. These can be found by applying the extended Euclidean algorithm
. It follows that there are also infinite solutions if c is a multiple of the greatest common divisor of a and b. If c is not a multiple of the greatest common divisor of a and b, then the Diophantine equation ax + by = c has no solutions.
, it is an exponential Diophantine equation. One example is the Ramanujan–Nagell equation, 2n − 7 = x2. Such equations do not have a general theory; 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
or even trial and error
.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, a Diophantine equation is an indeterminate
Indeterminate equation
An indeterminate equation, in mathematics, is an equation for which there is an infinite set of solutions; for example, 2x = y is a simple indeterminate equation. Indeterminate equations cannot be directly solved from the given information...
polynomial
Polynomial
In mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...
equation
Equation
An equation is a mathematical statement that asserts the equality of two expressions. In modern notation, this is written by placing the expressions on either side of an equals sign , for examplex + 3 = 5\,asserts that x+3 is equal to 5...
that allows the variable
Variable (mathematics)
In mathematics, a variable is a value that may change within the scope of a given problem or set of operations. In contrast, a constant is a value that remains unchanged, though often unknown or undetermined. The concepts of constants and variables are fundamental to many areas of mathematics and...
s to be integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
s only. Diophantine problems have fewer equations than unknown variables and involve finding integers that work correctly for all equations. In more technical language, they define an algebraic curve
Algebraic curve
In algebraic geometry, an algebraic curve is an algebraic variety of dimension one. The theory of these curves in general was quite fully developed in the nineteenth century, after many particular examples had been considered, starting with circles and other conic sections.- Plane algebraic curves...
, algebraic surface
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 and so of dimension four as a smooth manifold.The theory of algebraic surfaces is much more complicated than that...
, or more general object, and ask about the lattice points on it.
The word Diophantine refers to the Hellenistic
Hellenistic civilization
Hellenistic civilization represents the zenith of Greek influence in the ancient world from 323 BCE to about 146 BCE...
mathematician of the 3rd century, Diophantus
Diophantus
Diophantus of Alexandria , sometimes called "the father of algebra", was an Alexandrian Greek mathematician and the author of a series of books called Arithmetica. These texts deal with solving algebraic equations, many of which are now lost...
of Alexandria
Alexandria
Alexandria is the second-largest city of Egypt, with a population of 4.1 million, extending about along the coast of the Mediterranean Sea in the north central part of the country; it is also the largest city lying directly on the Mediterranean coast. It is Egypt's largest seaport, serving...
, who made a study of such equations and was one of the first mathematicians to introduce symbolism into algebra
Algebra
Algebra is the branch of mathematics concerning the study of the rules of operations and relations, and the constructions and concepts arising from them, including terms, polynomials, equations and algebraic structures...
. The mathematical study of Diophantine problems Diophantus initiated is now called "Diophantine analysis". A linear Diophantine equation is an equation between two sums of monomials of degree zero or one.
While individual equations present a kind of puzzle and have been considered throughout history, the formulation of general theories of Diophantine equations (beyond the theory of quadratic form
Quadratic form
In mathematics, a quadratic form is a homogeneous polynomial of degree two in a number of variables. For example,4x^2 + 2xy - 3y^2\,\!is a quadratic form in the variables x and y....
s) was an achievement of the twentieth century.
Examples of Diophantine equations
| In the following Diophantine equations, x, y, and z are the unknowns, the other letters being given are constants. | |
 | This is a linear Diophantine equation (see the section "Linear Diophantine equations" below). |
 | For n = 2 there are infinitely many solutions (x,y,z), the Pythagorean triple Pythagorean triple A Pythagorean triple consists of three positive integers a, b, and c, 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 k. A primitive Pythagorean triple is one in which a, b and c are pairwise coprime... s. For larger values of n, Fermat's Last Theorem Fermat's Last Theorem In number theory, Fermat's Last Theorem states that no three positive integers a, b, and c can satisfy the equation an + bn = cn for any integer value of n greater than two.... states that no positive integer solutions (x, y, z) satisfying the equation exist. |
 | (Pell's equation Pell's equation Pell's equation is any Diophantine equation of the formx^2-ny^2=1\,where n is a nonsquare integer. The word Diophantine means that integer values of x and y are sought. Trivially, x = 1 and y = 0 always solve this equation... ) which is named after the English mathematician John Pell John Pell -Early life:He was born at Southwick in Sussex. He was educated at Steyning Grammar School, and entered Trinity College, Cambridge, at the age of thirteen. During his university career he became an accomplished linguist, and even before he took his B.A. degree corresponded with Henry Briggs and... . It was studied by Brahmagupta Brahmagupta Brahmagupta was an Indian mathematician and astronomer who wrote many important works on mathematics and astronomy. His best known work is the Brāhmasphuṭasiddhānta , written in 628 in Bhinmal... in the 7th century, as well as by Fermat Pierre de Fermat Pierre de Fermat was a French lawyer at the Parlement of Toulouse, France, and an amateur mathematician who is given credit for early developments that led to infinitesimal calculus, including his adequality... in the 17th century. |
 | The Erdős–Straus conjecture Erdos–Straus conjecture In number theory, the Erdős–Straus conjecture states that for all integers n ≥ 2, the rational number 4/n can be expressed as the sum of three unit fractions. Paul Erdős and Ernst G... states that, for every positive integer n ≥ 2, there exists a solution with x, y, and z all positive integers. Although not usually stated in polynomial form, this example is equivalent to the polynomial equation 4xyz = yzn + xzn + xyn = n(yz + xz + xy). |
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
Given that a father's age is 1 less than twice that of his son, and that the digits AB making up the father's age are reversed in the son's age (ie. BA), leads to the equation 19B - 8A = 1. Inspection gives the result 73 and 37 years.17th and 18th centuries
In 1637, Pierre de FermatPierre de Fermat
Pierre de Fermat was a French lawyer at the Parlement of Toulouse, France, and an amateur mathematician who is given credit for early developments that led to infinitesimal calculus, including his adequality...
scribbled on the margin of his copy of Arithmetica
Arithmetica
Arithmetica 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 equations and indeterminate equations.Equations in the book are called Diophantine equations...
: "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 an + bn = cn has no solutions for any n higher than two." And then he wrote, intriguingly: "I have discovered a truly marvelous proof of this, which, however, the margin is not large enough to contain." Such a proof eluded mathematicians for centuries, however. As an unproven conjecture
Conjecture
A conjecture is a proposition that is unproven but is thought to be true and has not been disproven. Karl Popper pioneered the use of the term "conjecture" in scientific philosophy. Conjecture is contrasted by hypothesis , which is a testable statement based on accepted grounds...
that eluded brilliant mathematicians' attempts to either prove it or disprove it for generations, his statement became famous as Fermat's Last Theorem
Fermat's Last Theorem
In number theory, Fermat's Last Theorem states that no three positive integers a, b, and c can satisfy the equation an + bn = cn for any integer value of n greater than two....
. It wasn't until 1994 that it was proven by the British
United Kingdom
The United Kingdom of Great Britain and Northern IrelandIn the United Kingdom and Dependencies, other languages have been officially recognised as legitimate autochthonous languages under the European Charter for Regional or Minority Languages...
mathematician Andrew Wiles
Andrew Wiles
Sir Andrew John Wiles KBE FRS is a British mathematician and a Royal Society Research Professor at Oxford University, specializing in number theory...
.
In 1657, Fermat attempted the Diophantine equation 61x2 + 1 = y2 (solved by Brahmagupta
Brahmagupta
Brahmagupta was an Indian mathematician and astronomer who wrote many important works on mathematics and astronomy. His best known work is the Brāhmasphuṭasiddhānta , written in 628 in Bhinmal...
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.
Hilbert's tenth problem
In 1900, in recognition of their depth, David HilbertDavid Hilbert
David Hilbert was a German mathematician. He is recognized as one of the most influential and universal mathematicians of the 19th and early 20th centuries. Hilbert discovered and developed a broad range of fundamental ideas in many areas, including invariant theory and the axiomatization of...
proposed the solvability of all Diophantine problems as the tenth
Hilbert's tenth problem
Hilbert's tenth problem is the tenth on the list of Hilbert's problems of 1900. Its statement is as follows:Given a Diophantine equation with any number of unknown quantities and with rational integral numerical coefficients: To devise a process according to which it can be determined in a finite...
of his celebrated problems
Hilbert's problems
Hilbert's problems form a list of twenty-three problems in mathematics published by German mathematician David Hilbert in 1900. The problems were all unsolved at the time, and several of them were very influential for 20th century mathematics...
. In 1970, a novel result in mathematical logic
Mathematical logic
Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...
known as Matiyasevich's theorem settled the problem negatively: in general Diophantine problems are unsolvable.
Diophantine geometry, which is the application of techniques from algebraic geometry
Algebraic geometry
Algebraic geometry is a branch of mathematics which combines techniques of abstract algebra, especially commutative algebra, with the language and the problems of geometry. It occupies a central place in modern mathematics and has multiple conceptual connections with such diverse fields as complex...
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 system of simultaneous equations
Simultaneous equations
In mathematics, simultaneous equations are a set of equations containing multiple variables. This set is often referred to as a system of equations. A solution to a system of equations is a particular specification of the values of all variables that simultaneously satisfies all of the equations...
, which is a vector in a prescribed field
Field (mathematics)
In abstract algebra, a field is a commutative ring whose nonzero elements form a group under multiplication. As such it is an algebraic structure with notions of addition, subtraction, multiplication, and division, satisfying certain axioms...
K, when K is not algebraically closed.
Modern research
One of the few general approaches is through the Hasse principleHasse principle
In mathematics, Helmut Hasse's local-global principle, also known as the Hasse principle, is the idea that one can find an integer solution to an equation by using the Chinese remainder theorem to piece together solutions modulo powers of each different prime number...
. Infinite descent
Infinite descent
In mathematics, a proof by infinite descent is a particular kind of proof by contradiction which relies on the fact that the natural numbers are well ordered. One typical application is to show that a given equation has no solutions. Assuming a solution exists, one shows that another exists, that...
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 set
Diophantine set
In mathematics, a Diophantine equation is an equation of the form P=0 where P is a polynomial with integer coefficients...
s as equivalently described as recursively enumerable
Recursively enumerable set
In computability theory, traditionally called recursion theory, a set S of natural numbers is called recursively enumerable, computably enumerable, semidecidable, provable or Turing-recognizable if:...
. 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
Diophantine approximation
In number theory, the field of Diophantine approximation, named after Diophantus of Alexandria, deals with the approximation of real numbers by rational numbers....
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 most celebrated single question in the field, the conjecture
Conjecture
A conjecture is a proposition that is unproven but is thought to be true and has not been disproven. Karl Popper pioneered the use of the term "conjecture" in scientific philosophy. Conjecture is contrasted by hypothesis , which is a testable statement based on accepted grounds...
known as Fermat's Last Theorem
Fermat's Last Theorem
In number theory, Fermat's Last Theorem states that no three positive integers a, b, and c can satisfy the equation an + bn = cn for any integer value of n greater than two....
, was solved by Andrew Wiles
Andrew Wiles
Sir Andrew John Wiles KBE FRS is a British mathematician and a Royal Society Research Professor at Oxford University, specializing in number theory...
but 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' theorem
Faltings' theorem
In number theory, the Mordell conjecture is the conjecture made by that a curve of genus greater than 1 over the field Q of rational numbers has only finitely many rational points. The conjecture was later generalized by replacing Q by a finite extension...
, 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 (N) 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 N 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 N. Compare this to:
which doesn't always have a solution for positive N.
Linear Diophantine equations
Linear Diophantine equations take the form ax + by = c. If c is the greatest common divisorGreatest common divisor
In mathematics, the greatest common divisor , also known as the greatest common factor , or highest common factor , of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.For example, the GCD of 8 and 12 is 4.This notion can be extended to...
of a and b then this is Bézout's identity, and the equation has an infinite number of solutions. These can be found by applying the extended Euclidean algorithm
Extended Euclidean algorithm
The extended Euclidean algorithm is an extension to the Euclidean algorithm. Besides finding the greatest common divisor of integers a and b, as the Euclidean algorithm does, it also finds integers x and y that satisfy Bézout's identityThe extended Euclidean algorithm is particularly useful when a...
. It follows that there are also infinite solutions if c is a multiple of the greatest common divisor of a and b. If c is not a multiple of the greatest common divisor of a and b, then the Diophantine equation ax + by = c has no solutions.
Exponential Diophantine equations
If a Diophantine equation has as an additional variable or variables occurring as exponentsExponentiation
Exponentiation is a mathematical operation, written as an, involving two numbers, the base a and the exponent n...
, it is an exponential Diophantine equation. One example is the Ramanujan–Nagell equation, 2n − 7 = x2. Such equations do not have a general theory; 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
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 equations...
or even trial and error
Trial and error
Trial and error, or trial by error, is a general method of problem solving, fixing things, or for obtaining knowledge."Learning doesn't happen from failure itself but rather from analyzing the failure, making a change, and then trying again."...
.
External links
- Diophantine Equation. From MathWorldMathWorldMathWorld is an online mathematics reference work, created and largely written by Eric W. Weisstein. It is sponsored by and licensed to Wolfram Research, Inc. and was partially funded by the National Science Foundation's National Science Digital Library grant to the University of Illinois at...
at Wolfram Research. - Diophantine Equation. From PlanetMathPlanetMathPlanetMath is a free, collaborative, online mathematics encyclopedia. The emphasis is on rigour, openness, pedagogy, real-time content, interlinked content, and also community of about 24,000 people with various maths interests. Intended to be comprehensive, the project is hosted by the Digital...
. - Dario Alpern's Online Calculator. Retrieved 18 March 2009