Diophantine equation

In mathematics, a Diophantine equation is a polynomial equation 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. However, Hilbert's tenth problem shows that there cannot exist a general algorithm that can decide whether an arbitrary Diophantine equation has an integer solution (much less to find or characterize all such solutions).

The simplest linear Diophantine equation takes the form \[ax+by=c,\] where a, b and c are given integers. The solutions are described by the following theorem:

This Diophantine equation has a solution (where x and y are integers) if and only if c is a multiple of the greatest common divisor of a and b. Moreover, if (x, y) is a solution, then the other solutions have the form (x + kv, y − ku), where k is an arbitrary integer, and u and v are the quotients of a and b (respectively) 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 (eh, fh) is a solution. On the other hand, for every pair of 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 (x, y), we have \[\begin{aligned} a(x+kv) + b(y-ku) &= ax+by+k(av-bu) \\ &= ax+by+k(udv-vdu) \\ &= ax+by, \end{aligned}\] showing that (x + kv, y − ku) is another solution. Finally, given two solutions such that \[ax_1 + by_1 = ax_2 + by_2 = c,\] one deduces that \[u(x_2 - x_1) + v(y_2 - y_1) = 0.\] As u and v are coprime, Euclid's lemma shows that v divides x₂ − x₁, and thus that there exists an integer k such that both \[x_2 - x_1 = kv, \quad y_2 - y_1 = -ku.\] Therefore, \[x_2 = x_1 + kv, \quad y_2 = y_1 - ku,\] which completes the proof.

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

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 \[AX = C,\] where A is an m × n matrix of integers, X is an n × 1 column matrix of unknowns and C is an m × 1 column matrix of integers.

The computation of the Smith normal form of A provides two unimodular matrices (that is matrices that are invertible over the integers and have ±1 as determinant) U and V of respective dimensions m × m and n × n, such that the matrix \[B = [b_{i,j}] = UAV\] is such that b_i,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 \[B (V^{-1}X) = UC.\] Calling y_i the entries of VX and d_i those of D = UC, this leads to the system \[\begin{aligned} & b_{i,i}y_i = d_i, \quad 1 \leq i \leq k \\ & 0y_i = d_i, \quad k < i \leq n. \end{aligned}\]

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 = Vy for some column matrix of integers y such that By = D.

It follows that the system has a solution if and only if b_i,i divides d_i for i ≤ k and d_i = 0 for i > k. If this condition is fulfilled, the solutions of the given system are \[V\, \begin{bmatrix} \frac{d_1}{b_{1,1}}\\ \vdots\\ \frac{d_k}{b_{k,k}}\\ h_{k+1}\\ \vdots\\ h_n \end{bmatrix}\,,\] where h_k+1, …, h_n 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 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.

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

\(x^d+y^d -z^d=0.\)

As a homogeneous polynomial in n indeterminates defines a hypersurface in the projective space of dimension n − 1, 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 dth power of another rational number). A witness of the difficulty of the problem is Fermat's Last Theorem (for d > 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 example Faltings' 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.

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 p. For example, the Diophantine equation

\(x^2+y^2=3z^2,\)

does not have any other solution than the trivial solution (0, 0, 0). In fact, by dividing x, y, and z 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 x, y, and z are all even, and are thus not coprime. Thus the only solution is the trivial solution (0, 0, 0). This shows that there is no rational point on a circle of radius \(\sqrt{3}\), centered at the origin.

More generally, the Hasse-Minkowski theorem determines whether a homogeneous quadratic equation has a nontrivial rational solution by testing solvability over the real numbers and over the p-adic numbers; clearing denominators then gives a nontrivial integer solution.

If a non-trivial integer solution is known, one may produce all other solutions in the following way.

The questions asked in Diophantine analysis include:

1. Are there any solutions?
2. Are there any solutions beyond some that are easily found by inspection?
3. Are there finitely or infinitely many solutions?
4. Can all solutions be found in theory?
5. 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.

A father's age written in digits AB is the reverse of his son's age BA. Also the father's age is 1 less than twice the son's age. How old are they? The conditions lead to the equation 10A + B = 2(10B + A), 1, thus 19B, 8A = 1. A general method for such linear equations is given above, but mere inspection gives A = 7, B = 3, so that AB = 73 years and BA = 37 years. One may easily show this is the only solution where A and B are integer digits between 0 and 9.

Many well known puzzles in recreational mathematics lead to diophantine equations, such as the cannonball problem, Archimedes's cattle problem and the monkey and the coconuts.

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 a + b = c has no solutions for any n 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 61x + 1 = y (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 x = 226153980, y = 1766319049 (see Chakravala method).

In 1900, David Hilbert proposed the solvability of all Diophantine equations as the tenth of his fundamental problems: to find an algorithm to determine whether a given polynomial Diophantine equation with integer coefficients has an integer solution. 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.

The result rests on a stronger, positive statement. The MRDP theorem characterizes the sets of natural numbers that are Diophantine, those consisting of the values taken by one variable in the solutions of a polynomial equation, as exactly the recursively enumerable sets. Hilbert's tenth problem follows as a corollary, since there are recursively enumerable sets that are not decidable. The characterization also yields Diophantine representations of sets not usually described by equations, such as the prime numbers.

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 K, when K is not algebraically closed.

The oldest general method for solving a Diophantine equation, or for proving that there is no solution, 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.

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 a 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.

An example of an infinite Diophantine equation is: \[n = a^2 + 2b^2 + 3c^2 + 4d^2 + 5e^2 + \cdots,\] 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: \[n = a^2 + 4b^2 + 9c^2 + 16d^2 + 25e^2 + \cdots,\] which does not always have a solution for positive n.

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, 2 − 7 = x
• the equation of the Fermat-Catalan conjecture and Beal's conjecture, a + b = c with inequality restrictions on the exponents
• the Erdős-Moser equation, 1 + 2 + ⋯ + (m − 1) = m

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.