Diophantine equation

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

a(x + kv) + b(y − ku) = ax + by + k(av − bu) = ax + by + k(udv − vdu) = ax + by,

showing that (x + kv, y − ku) is another solution. Finally, given two solutions such that ax₁ + by₁ = ax₂ + by₂ = c, one deduces that u(x₂ − x₁) + v(y₂ − y₁) = 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 x₂ − x₁ = kv and y₂ − y₁ = −ku. Therefore, x₂ = x₁ + kv and y₂ = y₁ − ku, which completes the proof.

The Chinese remainder theorem describes an important class of linear Diophantine systems of equations: let n₁, …, n_k be k pairwise coprime integers greater than one, a₁, …, a_k be k arbitrary integers, and N be the product n₁ ⋯ n_k. The Chinese remainder theorem asserts that the following linear Diophantine system has exactly one solution (x, x₁, …, x_k) such that 0 ≤ x < N, and that the other solutions are obtained by adding to x a multiple of N:

${\displaystyle {\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

A X = 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⁻¹X) = UC.

Calling y_i the entries of V⁻¹X and d_i those of D = UC, this leads to the system

b_i,i y_i = d_i for 1 ≤ i ≤ k,

0 y_i = d_i 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 = 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

${\displaystyle 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."[6]

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.[7]

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

${\displaystyle 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 ${\displaystyle {\sqrt {3}},}$ centered at the origin.

More generally, the Hasse 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.

Let

${\displaystyle Q(x_{1},\ldots ,x_{n})=0}$

be a homogeneous Diophantine equation, where ${\displaystyle Q(x_{1},\ldots ,x_{n})}$ is a quadratic form (that is, a homogeneous polynomial of degree 2), with integer coefficients. The trivial solution is the solution where all ${\displaystyle x_{i}}$ are zero. If ${\displaystyle (a_{1},\ldots ,a_{n})}$ is a non-trivial integer solution of this equation, then ${\displaystyle \left(a_{1},\ldots ,a_{n}\right)}$ are the homogeneous coordinates of a rational point of the hypersurface defined by Q. Conversely, if ${\textstyle \left({\frac {p_{1}}{q}},\ldots ,{\frac {p_{n}}{q}}\right)}$ are homogeneous coordinates of a rational point of this hypersurface, where ${\displaystyle q,p_{1},\ldots ,p_{n}}$ are integers, then ${\displaystyle \left(p_{1},\ldots ,p_{n}\right)}$ is an integer solution of the Diophantine equation. Moreover, the integer solutions that define a given rational point are all sequences of the form

${\displaystyle \left(k{\frac {p_{1}}{d}},\ldots ,k{\frac {p_{n}}{d}}\right),}$

where k is any integer, and d is the greatest common divisor of the ${\displaystyle p_{i}.}$

It follows that solving the Diophantine equation ${\displaystyle Q(x_{1},\ldots ,x_{n})=0}$ is completely reduced to finding the rational points of the corresponding projective hypersurface.

Let now ${\displaystyle A=\left(a_{1},\ldots ,a_{n}\right)}$ be an integer solution of the equation ${\displaystyle Q(x_{1},\ldots ,x_{n})=0.}$ As Q is a polynomial of degree two, a line passing through A 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 A, 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 ${\displaystyle a_{n}\neq 0.}$ Then one may pass to the affine case by considering the affine hypersurface defined by

${\displaystyle q(x_{1},\ldots ,x_{n-1})=Q(x_{1},\ldots ,x_{n-1},1),}$

which has the rational point

${\displaystyle R=(r_{1},\ldots ,r_{n-1})=\left({\frac {a_{1}}{a_{n}}},\ldots ,{\frac {a_{n-1}}{a_{n}}}\right).}$

If this rational point is a singular point, that is if all partial derivatives are zero at R, all lines passing through R are contained in the hypersurface, and one has a cone. The change of variables

${\displaystyle y_{i}=x_{i}-r_{i}}$

does not change the rational points, and transforms q into a homogeneous polynomial in n − 1 variables. In this case, the problem may thus be solved by applying the method to an equation with fewer variables.

If the polynomial q is a product of linear polynomials (possibly with non-rational coefficients), then it defines two hyperplanes. 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 R:

${\displaystyle {\begin{aligned}x_{2}&=r_{2}+t_{2}(x_{1}-r_{1})\\&\;\;\vdots \\x_{n-1}&=r_{n-1}+t_{n-1}(x_{1}-r_{1}).\end{aligned}}}$

Substituting this in q, one gets a polynomial of degree two in ${\displaystyle x_{1},}$ that is zero for ${\displaystyle x_{1}=r_{1}.}$ It is thus divisible by ${\displaystyle x_{1}-r_{1},}$. The quotient is linear in ${\displaystyle x_{1},}$ and may be solved for expressing ${\displaystyle x_{1}}$ as a quotient of two polynomials of degree at most two in ${\displaystyle t_{2},\ldots ,t_{n-1},}$ with integer coefficients:

${\displaystyle x_{1}={\frac {f_{1}(t_{2},\ldots ,t_{n-1})}{f_{n}(t_{2},\ldots ,t_{n-1})}}.}$

Substituting this in the expressions for ${\displaystyle x_{2},\ldots ,x_{n-1},}$ one gets, for i = 1, …, n − 1,

${\displaystyle x_{i}={\frac {f_{i}(t_{2},\ldots ,t_{n-1})}{f_{n}(t_{2},\ldots ,t_{n-1})}},}$

where ${\displaystyle f_{1},\ldots ,f_{n}}$ are polynomials of degree at most two with integer coefficients.

Then, one can return to the homogeneous case. Let, for i = 1, …, n,

${\displaystyle F_{i}(t_{1},\ldots ,t_{n-1})=t_{1}^{2}f_{i}\left({\frac {t_{2}}{t_{1}}},\ldots ,{\frac {t_{n-1}}{t_{1}}}\right),}$

be the homogenization of ${\displaystyle f_{i}.}$ These quadratic polynomials with integer coefficients form a parameterization of the projective hypersurface defined by Q:

${\displaystyle {\begin{aligned}x_{1}&=F_{1}(t_{1},\ldots ,t_{n-1})\\&\;\;\vdots \\x_{n}&=F_{n}(t_{1},\ldots ,t_{n-1}).\end{aligned}}}$

A point of the projective hypersurface defined by Q is rational if and only if it may be obtained from rational values of ${\displaystyle t_{1},\ldots ,t_{n-1}.}$ As ${\displaystyle F_{1},\ldots ,F_{n}}$ are homogeneous polynomials, the point is not changed if all ${\displaystyle t_{i}}$ are multiplied by the same rational number. Thus, one may suppose that ${\displaystyle t_{1},\ldots ,t_{n-1}}$ are coprime integers. It follows that the integer solutions of the Diophantine equation are exactly the sequences ${\displaystyle (x_{1},\ldots ,x_{n})}$ where, for i = 1, ..., n,

${\displaystyle x_{i}=k\,{\frac {F_{i}(t_{1},\ldots ,t_{n-1})}{d}},}$

where k is an integer, ${\displaystyle t_{1},\ldots ,t_{n-1}}$ are coprime integers, and d is the greatest common divisor of the n integers ${\displaystyle F_{i}(t_{1},\ldots ,t_{n-1}).}$

One could hope that the coprimality of the ${\displaystyle t_{i}}$ could imply that d = 1. Unfortunately this is not the case, as shown in the next section.

The equation

${\displaystyle x^{2}+y^{2}-z^{2}=0}$

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 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:

${\displaystyle y=t(x+1).}$

Putting this in the circle equation

${\displaystyle x^{2}+y^{2}-1=0,}$

one gets

${\displaystyle x^{2}-1+t^{2}(x+1)^{2}=0.}$

Dividing by x + 1, results in

${\displaystyle x-1+t^{2}(x+1)=0,}$

which is easy to solve in x:

${\displaystyle x={\frac {1-t^{2}}{1+t^{2}}}.}$

It follows

${\displaystyle y=t(x+1)={\frac {2t}{1+t^{2}}}.}$

Homogenizing as described above one gets all solutions as

${\displaystyle {\begin{aligned}x&=k\,{\frac {s^{2}-t^{2}}{d}}\\y&=k\,{\frac {2st}{d}}\\z&=k\,{\frac {s^{2}+t^{2}}{d}},\end{aligned}}}$

where k is any integer, s and t are coprime integers, and d is the greatest common divisor of the three numerators. In fact, d = 2 if s and t are both odd, and d = 1 if one is odd and the other is even.

The primitive triples are the solutions where k = 1 and s > t > 0.

This description of the solutions differs slightly from Euclid's formula because Euclid's formula considers only the solutions such that x, y and z are all positive, and does not distinguish between two triples that differ by the exchange of x and y,

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.

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 (i.e. BA). This leads to the equation 10A + B = 2(10B + A) − 1, thus 19B − 8A = 1. Inspection gives the result A = 7, B = 3, and thus AB equals 73 years and BA equals 37 years. One may easily show that there is not any other solution with A and B 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.

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

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.

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 single most celebrated question in the field, the conjecture known as Fermat's Last Theorem, was solved by Andrew Wiles,[3] 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.

An example of an infinite diophantine equation is:

n = a² + 2b² + 3c² + 4d² + 5e² + ⋯, 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.[9] Compare this to:

n = a² + 4b² + 9c² + 16d² + 25e² + ⋯,

which does not always have a solution for positive n.