Inmathematics, aDiophantine equation is apolynomial equation withinteger coefficients, for which only integer solutions are of interest. Alinear Diophantine equation equates the sum of two or more unknowns, with coefficients, to a constant. Anexponential Diophantine equation is one in which unknowns can appear inexponents.
The wordDiophantine refers to theHellenistic mathematician of the 3rd century,Diophantus ofAlexandria, who made a study of such equations and was one of the first mathematicians to introducesymbolism intoalgebra. The mathematical study of Diophantine problems that Diophantus initiated is now calledDiophantine 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 andquadratic equations, was an achievement of the twentieth century.
Forn = 2 there are infinitely many solutions(x, y, z): thePythagorean triples. For larger integer values ofn,Fermat's Last Theorem (initially claimed in 1637 by Fermat andproved by Andrew Wiles in 1995[3]) states there are no positive integer solutions(x, y, z).
This isPell's equation, which is named after the English mathematicianJohn Pell. It was studied byBrahmagupta in the 7th century, as well as by Fermat in the 17th century.
TheErdős–Straus conjecture states that, for every positive integern ≥ 2, there exists a solution inx, y, andz, all as positive integers. Although not usually stated in polynomial form, this example is equivalent to the polynomial equation
Conjectured incorrectly byEuler to have no nontrivial solutions. Proved byElkies to have infinitely many nontrivial solutions, with a computer search by Frye determining the smallest nontrivial solution,958004 + 2175194 + 4145604 = 4224814.[4][5]
The simplest linear Diophantine equation takes the form wherea,b andc are given integers. The solutions are described by the following theorem:
This Diophantine equation has a solution (wherex andy are integers)if and only ifcis a multiple of thegreatest common divisor ofaandb.Moreover, if(x, y)is a solution, then the other solutions have the form(x +kv, y −ku),wherekis an arbitrary integer, anduandvare the quotients ofaandb(respectively) by the greatest common divisor ofaandb.
Proof: Ifd is this greatest common divisor,Bézout's identity asserts the existence of integerse andf such thatae +bf =d. Ifc is a multiple ofd, thenc =dh for some integerh, and(eh, fh) is a solution. On the other hand, for every pair of integersx andy, the greatest common divisord ofa andb dividesax +by. Thus, if the equation has a solution, thenc must be a multiple ofd. Ifa =ud andb =vd, then for every solution(x, y), we have showing that(x +kv, y −ku) is another solution. Finally, given two solutions such that one deduces that Asu andv arecoprime,Euclid's lemma shows thatv dividesx2 −x1, and thus that there exists an integerk such that both Therefore,which completes the proof.
TheChinese remainder theorem describes an important class of linear Diophantine systems of equations: let bekpairwise coprime integers greater than one, bek arbitrary integers, andN be the product The Chinese remainder theorem asserts that the following linear Diophantine system has exactly one solution such that0 ≤x <N, and that the other solutions are obtained by adding tox a multiple ofN:
More generally, every system of linear Diophantine equations may be solved by computing theSmith normal form of its matrix, in a way that is similar to the use of thereduced row echelon form to solve asystem of linear equations over a field. Usingmatrix notation every system of linear Diophantine equations may be writtenwhereA is anm ×n matrix of integers,X is ann × 1column matrix of unknowns andC is anm × 1 column matrix of integers.
The computation of the Smith normal form ofA provides twounimodular matrices (that is matrices that are invertible over the integers and have ±1 as determinant)U andV of respective dimensionsm ×m andn ×n, such that the matrixis such thatbi,i is not zero fori not greater than some integerk, and all the other entries are zero. The system to be solved may thus be rewritten asCallingyi the entries ofV−1X anddi those ofD =UC, this leads to the system
This system is equivalent to the given one in the following sense: A column matrix of integersx is a solution of the given system if and only ifx =Vy for some column matrix of integersy such thatBy =D.
It follows that the system has a solution if and only ifbi,i dividesdi fori ≤k anddi = 0 fori >k. If this condition is fulfilled, the solutions of the given system arewherehk+1, …,hn 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."[6]
Integer linear programming amounts to finding some integer solutions (optimal in some sense) of linear systems that include alsoinequations. 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.[7]
As a homogeneous polynomial inn indeterminates defines ahypersurface in theprojective space of dimensionn − 1, solving a homogeneous Diophantine equation is the same as finding therational 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 arational number is thedth power of another rational number). A witness of the difficulty of the problem is Fermat's Last Theorem (ford > 2, 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 exampleFalting'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.[8]
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 equationmodulop. For example, the Diophantine equation
does not have any other solution than the trivial solution(0, 0, 0). In fact, by dividingx, y, andz by theirgreatest common divisor, one may suppose that they arecoprime. 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 ifx, y, andz are all even, and are thus not coprime. Thus the only solution is the trivial solution(0, 0, 0). This shows that there is norational point on acircle of radius, centered at the origin.
More generally, theHasse 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.
be a homogeneous Diophantine equation, where is aquadratic form (that is, a homogeneous polynomial of degree 2), with integer coefficients. Thetrivial solution is the solution where all are zero. If is a non-trivial integer solution of this equation, then are thehomogeneous coordinates of arational point of the hypersurface defined byQ. 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
wherek is any integer, andd 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.
Let now be an integer solution of the equation AsQ is a polynomial of degree two, a line passing throughA 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 throughA, 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 theaffine hypersurface defined by
which has the rational point
If this rational point is asingular point, that is if allpartial derivatives are zero atR, all lines passing throughR are contained in the hypersurface, and one has acone. The change of variables
does not change the rational points, and transformsq into a homogeneous polynomial inn − 1 variables. In this case, the problem may thus be solved by applying the method to an equation with fewer variables.
If the polynomialq is a product of linear polynomials (possibly with non-rational coefficients), then it defines twohyperplanes. The intersection of these hyperplanes is a rationalflat, and contains rational singular points. This case is thus a special instance of the preceding case.
In the general case, consider theparametric equation of a line passing throughR:
Substituting this inq, one gets a polynomial of degree two inx1, that is zero forx1 =r1. It is thus divisible byx1 −r1. The quotient is linear inx1, and may be solved for expressingx1 as a quotient of two polynomials of degree at most two in with integer coefficients:
Substituting this in the expressions for one gets, fori = 1, …,n − 1,
where are polynomials of degree at most two with integer coefficients.
Then, one can return to the homogeneous case. Let, fori = 1, …,n,
be thehomogenization of These quadratic polynomials with integer coefficients form a parameterization of the projective hypersurface defined byQ:
A point of the projective hypersurface defined byQ is rational if and only if it may be obtained from rational values of As are homogeneous polynomials, the point is not changed if allti are multiplied by the same rational number. Thus, one may suppose that arecoprime integers. It follows that the integer solutions of the Diophantine equation are exactly the sequences where, fori = 1, ...,n,
wherek is an integer, are coprime integers, andd is the greatest common divisor of then integers
One could hope that the coprimality of theti, could imply thatd = 1. Unfortunately this is not the case, as shown in the next section.
is probably the first homogeneous Diophantine equation of degree two that has been studied. Its solutions are thePythagorean triples. This is also the homogeneous equation of theunit circle. In this section, we show how the above method allows retrievingEuclid's formula for generating Pythagorean triples.
For retrieving exactly Euclid's formula, we start from the solution(−1, 0, 1), corresponding to the point(−1, 0) 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 byx + 1, results in
which is easy to solve inx:
It follows
Homogenizing as described above one gets all solutions as
wherek is any integer,s andt are coprime integers, andd is the greatest common divisor of the three numerators. In fact,d = 2 ifs andt are both odd, andd = 1 if one is odd and the other is even.
Theprimitive triples are the solutions wherek = 1 ands >t > 0.
This description of the solutions differs slightly from Euclid's formula because Euclid's formula considers only the solutions such thatx, y, andz are all positive, and does not distinguish between two triples that differ by the exchange ofx andy,
The questions asked in Diophantine analysis include:
Are there any solutions?
Are there any solutions beyond some that are easily found byinspection?
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.
The given information is that a father's age is 1 less than twice that of his son, and that the digitsAB making up the father's age are reversed in the son's age (i.e.BA). This leads to the equation10A +B = 2(10B +A) − 1, thus19B − 8A = 1. Inspection gives the resultA = 7,B = 3, and thusAB equals 73 years andBA equals 37 years. One may easily show that there is not any other solution withA andB positive integers less than 10.
In 1637,Pierre de Fermat scribbled on the margin of his copy ofArithmetica: "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 equationan +bn =cn has no solutions for anyn 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 asFermat's Last Theorem. It was not until 1995 that it was proven by the British mathematicianAndrew Wiles.
In 1657, Fermat attempted to solve the Diophantine equation61x2 + 1 =y2 (solved byBrahmagupta over 1000 years earlier). The equation was eventually solved byEuler in the early 18th century, who also solved a number of other Diophantine equations. The smallest solution of this equation in positive integers isx = 226153980,y = 1766319049 (seeChakravala method).
The oldest general method for solving a Diophantine equation—or for proving that there is no solution— is the method ofinfinite descent, which was introduced byPierre de Fermat. Another general method is theHasse principle that usesmodular 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 byHilbert's tenth problem, which was set in 1900 byDavid 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 usingalgebraic geometry. In fact, a Diophantine equation can be viewed as the equation of ahypersurface, and the solutions of the equation are the points of the hypersurface that have integer coordinates.
This approach led eventually to theproof by Andrew Wiles in 1994 ofFermat's Last Theorem, stated without proof around 1637. This is another illustration of the difficulty of solving Diophantine equations.
An example of an infinite Diophantine equation is:which can be expressed as "How many ways can a given integern 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 eachn forms an integer sequence. Infinite Diophantine equations are related totheta functions and infinite dimensional lattices. This equation always has a solution for any positiven.[9] Compare this to:which does not always have a solution for positiven.
If a Diophantine equation has as an additional variable or variables occurring asexponents, it is an exponential Diophantine equation. Examples include:
^Frye, Roger E. (1988). "Finding 958004 + 2175194 + 4145604 = 4224814 on the Connection Machine".Proceedings of Supercomputing 88, Vol.II: Science and Applications. pp. 106–116.doi:10.1109/SUPERC.1988.74138.
^Richard Zippel (1993).Effective Polynomial Computation. Springer Science & Business Media. p. 50.ISBN978-0-7923-9375-7.
^Alexander Bockmayr, Volker Weispfenning (2001). "Solving Numerical Constraints". In John Alan Robinson and Andrei Voronkov (ed.).Handbook of Automated Reasoning Volume I. Elsevier and MIT Press. p. 779.ISBN0-444-82949-0. (Elsevier) (MIT Press).
Bachmakova, Isabelle (1966). "Diophante et Fermat".Revue d'Histoire des Sciences et de Leurs Applications.19 (4):289–306.doi:10.3406/rhs.1966.2507.JSTOR23905707.
Bashmakova, Izabella G.Diophantus and Diophantine Equations. Moscow: Nauka 1972 [in 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., Slavutin, E. I.History of Diophantine Analysis from Diophantus to Fermat. Moscow: Nauka 1984 [in 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.
Grechuk, Bogdan (2024).Polynomial Diophantine Equations: A Systematic Approach. Springer.ISBN9783031629488.
Rashed, Roshdi (2013).Histoire de l'analyse diophantienne classique: D'Abū Kāmil à Fermat (in French). Berlin; New York: Walter de Gruyter.ISBN978-3-11-033788-4.
