In mathematics, a Diophantine equation is a polynomial equation in two or more unknowns
such that only the integer solutions are searched or studied. A linear Diophantine equation
is an equation between two sums of monomials of degree zero or one. An exponential Diophantine
equation is one in which exponents on terms can be unknowns.
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 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 was an achievement
of the twentieth century.
Examples In the following Diophantine equations, x,
y, and z are the unknowns and the other letters are given constants:
Linear Diophantine equations One equation
The simplest linear Diophantine equation takes the form ax + by = c, where a, b and c are
given integers. The solutions are completely described by the following theorem: This Diophantine
equation has a solution if and only if c is a multiple of the greatest common divisor
of a and b. Moreover, if is a solution, then the other solutions have the form, where k
is an arbitrary integer, and u and v are the quotients of a and b by the greatest common
divisor of a and b. Proof: If d is this greatest common divisor,
Bézout's identity asserts the existence of integers e and f such that ae + bf = d. If
c is a multiple of d, then c = dh for some integer h, and is a solution. On the other
hand, for every integers x and y, the greatest common divisor d of a and b divides ax + by.
Thus, if the equation has a solution, then c must be a multiple of d. If a = ud and b
= vd, then for every solution, we have ,
showing that is another solution. Finally, given two solutions such that ax1 + by1 = ax2
+ by2 = c, one deduces that u + v = 0. As u and v are coprime, Euclid's lemma shows
that there exists an integer k such that x2 - x1 = kv and y2 - y1 = -ku. Therefore x2
= x1 + kv and y2 = y1 - kv, which completes the proof.
Chinese remainder theorem The Chinese remainder theorem describes an
important class of linear Diophantine systems of equations: let n1, ..., nk be k pairwise
coprime integers greater than one, a1, ..., ak be k arbitrary integers, and N be the product
n1 ··· nk. The Chinese remainder theorem asserts that the following linear Diophantine
system has exactly one solution such that 0 ≤ x < N, and that the other solutions
are obtained by adding to x a multiple of N:
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 A is a m×n matrix of integers, X is a n×1 column matrix of unknowns and C is
a m×1 column matrix of integers. The computation of the Smith normal form of
A provides two unimodular matrices U and V of respective dimensions m×m and n×n, such
that the matrix
is such that bi,i is not zero for i not greater than some integer k, and all the other entries
are zero. The system to be solved may thus be rewritten as
Calling yi the entries of and di those of this leads to the system
bi,i yi = di for 1 ≤ i ≤ k, 0 yi = di for k < i ≤ n.
This system is equivalent to the given one in the following sense: A column matrix of
integers x is a solution of the given system if and only if x = V y for some column matrix
of integers y such that By = D. It follows that the system has a solution
if and only if bi,i divides di for i ≤ k and di = 0 for i > k. If this condition is
fulfilled, the solutions of the given system are
where hk+1, ..., hn are arbitrary integers. 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, 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 AB making up the father's
age are reversed in the son's age. This leads to the equation 10A + B = 2 - 1, thus 19B
- 8A = 1. Inspection gives the result A = 7, B = 3, and thus AB = 73 years and BA = 37
years. One may easily show that there is not any other solution with A and B positive integers
less than 10. 17th and 18th centuries
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 an + bn = cn has no solutions for any n higher than 2." And then
he wrote, intriguingly: "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 wasn't
until 1995 that it was proven by the British mathematician Andrew Wiles.
In 1657, Fermat attempted to solve the Diophantine equation 61x2 + 1 = y2. 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 x = 226153980, y = 1766319049.
Hilbert's tenth problem In 1900, in recognition of their depth, David
Hilbert 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 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 a system of polynomial equations, which
is a vector in a prescribed field K, when K is not algebraically closed.
Modern research One of the few general approaches is through
the Hasse principle. 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 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 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.
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 does not always have a solution for positive N.
Exponential Diophantine equations If a Diophantine equation has as an additional
variable or variables occurring as exponents, it is an exponential Diophantine equation.
One example is the Ramanujan–Nagell equation, 2n − 7 = x2. 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 or even trial and
error. Notes
References Mordell, L. J.. Diophantine equations. Pure
and Applied Mathematics 30. Academic Press. ISBN 0-12-506250-8. Zbl 0188.34503.
Schmidt, Wolfgang M.. Diophantine approximations and Diophantine equations. Lecture Notes in
Mathematics 1467. Berlin: Springer-Verlag. ISBN 3-540-54058-X. Zbl 0754.11020.
Shorey, T. N.; Tijdeman, R.. Exponential Diophantine equations. Cambridge Tracts in Mathematics
87. Cambridge University Press. ISBN 0-521-26826-5. Zbl 0606.10011.
Smart, Nigel P.. The algorithmic resolution of Diophantine equations. London Mathematical
Society Student Texts 41. Cambridge University Press. ISBN 0-521-64156-X. Zbl 0907.11001.
Stillwell, John. Mathematics and its History. Springer Science + Business Media Inc. ISBN 0-387-95336-1.
Further reading Dickson, Leonard Eugene [1920]. History of
the Theory of Numbers. Volume II: Diophantine analysis. Mineola, NY: Dover Publications.
ISBN 978-0-486-44233-4. MR 0245500. Zbl 1214.11002. External links
Diophantine Equation. From MathWorld at Wolfram Research.
Diophantine Equation. From PlanetMath. Hazewinkel, Michiel, ed., "Diophantine equations",
Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4 Dario Alpern's Online Calculator. Retrieved
18 March 2009