fbpx
Wikipedia

Diophantine equation

In mathematics, a Diophantine equation is an equation, typically a polynomial equation in two or more unknowns with integer coefficients, such that the only solutions of interest are the integer ones. A linear Diophantine equation equates to a constant the sum of two or more monomials, each of degree one. An exponential Diophantine equation is one in which unknowns can appear in exponents.

Finding all right triangles with integer side-lengths is equivalent to solving the Diophantine equation

Diophantine problems have fewer equations than unknowns and involve finding integers that solve simultaneously all equations. As 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.

Examples

In the following Diophantine equations, w, x, y, and z are the unknowns and the other letters are given constants:

  This is a linear Diophantine equation.
  The smallest nontrivial solution in positive integers is 123 + 13 = 93 + 103 = 1729. It was famously given as an evident property of 1729, a taxicab number (also named Hardy–Ramanujan number) by Ramanujan to Hardy while meeting in 1917.[1] There are infinitely many nontrivial solutions.[2]
  For n = 2 there are infinitely many solutions (x, y, z): the Pythagorean triples. For larger integer values of n, Fermat's Last Theorem (initially claimed in 1637 by Fermat and proved by Andrew Wiles in 1995[3]) states there are no positive integer solutions (x, y, z).
  This is Pell's equation, which is named after the English mathematician John Pell. It was studied by Brahmagupta in the 7th century, as well as by Fermat in the 17th century.
  The Erdős–Straus conjecture states that, for every positive integer n ≥ 2, there exists a solution in x, y, and z, all as positive integers. Although not usually stated in polynomial form, this example is equivalent to the polynomial equation  
  Conjectured incorrectly by Euler to have no nontrivial solutions. Proved by Elkies to have infinitely many nontrivial solutions, with a computer search by Frye determining the smallest nontrivial solution, 958004 + 2175194 + 4145604 = 4224814.[4][5]

Linear Diophantine equations

One equation

The simplest linear Diophantine equation takes the form

 
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, yku), 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

 
showing that (x + kv, yku) is another solution. Finally, given two solutions such that
 
one deduces that
 
As u and v are coprime, Euclid's lemma shows that v divides x2x1, and thus that there exists an integer k such that both
 
Therefore,
 
which completes the proof.

Chinese remainder theorem

The Chinese remainder theorem describes an important class of linear Diophantine systems of equations: let   be k pairwise coprime integers greater than one,   be k arbitrary integers, and N be the product   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 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

 
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 V−1X and di those of D = UC, this leads to the system
 
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 bi,i divides di for ik 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.

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

 

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 Falting'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]

Degree two

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

 

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

Geometric interpretation

Let

 

be a homogeneous Diophantine equation, where   is a quadratic form (that is, a homogeneous polynomial of degree 2), with integer coefficients. The trivial solution is the solution where all   are zero. If   is a non-trivial integer solution of this equation, then   are the homogeneous coordinates of a rational point of the hypersurface defined by Q. 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

 

where k is any integer, and d 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.

Parameterization

Let now   be an integer solution of the equation   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   Then one may pass to the affine case by considering the affine hypersurface defined by

 

which has the rational point

 

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

 

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:

 

Substituting this in q, one gets a polynomial of degree two in x1, that is zero for x1 = r1. It is thus divisible by x1r1. The quotient is linear in x1, and may be solved for expressing x1 as a quotient of two polynomials of degree at most two in   with integer coefficients:

 

Substituting this in the expressions for   one gets, for i = 1, …, n − 1,

 

where   are polynomials of degree at most two with integer coefficients.

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

 

be the homogenization of   These quadratic polynomials with integer coefficients form a parameterization of the projective hypersurface defined by Q:

 

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

 

where k is an integer,   are coprime integers, and d is the greatest common divisor of the n integers  

One could hope that the coprimality of the ti, could imply that d = 1. Unfortunately this is not the case, as shown in the next section.

Example of Pythagorean triples

The equation

 

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:

 

Putting this in the circle equation

 

one gets

 

Dividing by x + 1, results in

 

which is easy to solve in x:

 

It follows

 

Homogenizing as described above one gets all solutions as

 

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,

Diophantine analysis

Typical questions

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.

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

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." 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 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. The smallest solution of this equation in positive integers is x = 226153980, y = 1766319049 (see Chakravala method).

Hilbert's tenth problem

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

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

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.[9] 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. Examples include the Ramanujan–Nagell equation, 2n − 7 = x2, and the equation of the Fermat–Catalan conjecture and Beal's conjecture, am + bn = ck with inequality restrictions on the exponents. 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.

See also

Notes

  1. ^ . Gap.dcs.st-and.ac.uk. Archived from the original on 16 July 2012. Retrieved 20 November 2012.
  2. ^ Everest, G.; Ward, Thomas (2006), An Introduction to Number Theory, Graduate Texts in Mathematics, vol. 232, Springer, p. 117, ISBN 9781846280443.
  3. ^ a b Wiles, Andrew (1995). "Modular elliptic curves and Fermat's Last Theorem" (PDF). Annals of Mathematics. 141 (3): 443–551. doi:10.2307/2118559. JSTOR 2118559. OCLC 37032255.
  4. ^ Elkies, Noam (1988). "On A4 + B4 + C4 = D4" (PDF). Mathematics of Computation. 51 (184): 825–835. doi:10.2307/2008781. JSTOR 2008781. MR 0930224.
  5. ^ 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.
  6. ^ Richard Zippel (1993). Effective Polynomial Computation. Springer Science & Business Media. p. 50. ISBN 978-0-7923-9375-7.
  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. ISBN 0-444-82949-0. (Elsevier) (MIT Press).
  8. ^ Kovacic, Jerald (8 May 1985). "An Algorithm for Solving Second Order Linear Homogeneous Differential Equations" (PDF). Core. (PDF) from the original on 16 April 2019.
  9. ^ "A320067 - Oeis".

References

Further reading

  • 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. JSTOR 23905707.
  • 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. " Historia Mathematica 8 (1981), 393–416.
  • 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.
  • Dickson, Leonard Eugene (2005) [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.
  • Rashed, Roshdi; Houzel, Christian (2013). Les "Arithmétiques" de Diophante. doi:10.1515/9783110336481. ISBN 978-3-11-033593-4.
  • Rashed, Roshdi, Histoire de l'analyse diophantienne classique : D'Abū Kāmil à Fermat, Berlin, New York : Walter de Gruyter.

External links

diophantine, equation, mathematics, equation, typically, polynomial, equation, more, unknowns, with, integer, coefficients, such, that, only, solutions, interest, integer, ones, linear, equates, constant, more, monomials, each, degree, exponential, which, unkn. In mathematics a Diophantine equation is an equation typically a polynomial equation in two or more unknowns with integer coefficients such that the only solutions of interest are the integer ones A linear Diophantine equation equates to a constant the sum of two or more monomials each of degree one An exponential Diophantine equation is one in which unknowns can appear in exponents Finding all right triangles with integer side lengths is equivalent to solving the Diophantine equation a 2 b 2 c 2 displaystyle a 2 b 2 c 2 Diophantine problems have fewer equations than unknowns and involve finding integers that solve simultaneously all equations As 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 Contents 1 Examples 2 Linear Diophantine equations 2 1 One equation 2 2 Chinese remainder theorem 2 3 System of linear Diophantine equations 3 Homogeneous equations 3 1 Degree two 3 1 1 Geometric interpretation 3 1 2 Parameterization 3 1 3 Example of Pythagorean triples 4 Diophantine analysis 4 1 Typical questions 4 2 Typical problem 4 3 17th and 18th centuries 4 4 Hilbert s tenth problem 4 5 Diophantine geometry 4 6 Modern research 4 7 Infinite Diophantine equations 5 Exponential Diophantine equations 6 See also 7 Notes 8 References 9 Further reading 10 External linksExamples EditIn the following Diophantine equations w x y and z are the unknowns and the other letters are given constants a x b y c displaystyle ax by c This is a linear Diophantine equation w 3 x 3 y 3 z 3 displaystyle w 3 x 3 y 3 z 3 The smallest nontrivial solution in positive integers is 123 13 93 103 1729 It was famously given as an evident property of 1729 a taxicab number also named Hardy Ramanujan number by Ramanujan to Hardy while meeting in 1917 1 There are infinitely many nontrivial solutions 2 x n y n z n displaystyle x n y n z n For n 2 there are infinitely many solutions x y z the Pythagorean triples For larger integer values of n Fermat s Last Theorem initially claimed in 1637 by Fermat and proved by Andrew Wiles in 1995 3 states there are no positive integer solutions x y z x 2 n y 2 1 displaystyle x 2 ny 2 pm 1 This is Pell s equation which is named after the English mathematician John Pell It was studied by Brahmagupta in the 7th century as well as by Fermat in the 17th century 4 n 1 x 1 y 1 z displaystyle frac 4 n frac 1 x frac 1 y frac 1 z The Erdos Straus conjecture states that for every positive integer n 2 there exists a solution in x y and z all as positive integers Although not usually stated in polynomial form this example is equivalent to the polynomial equation x y z y z n x z n x y n n y z x z x y displaystyle xyz yzn xzn xyn n yz xz xy x 4 y 4 z 4 w 4 displaystyle x 4 y 4 z 4 w 4 Conjectured incorrectly by Euler to have no nontrivial solutions Proved by Elkies to have infinitely many nontrivial solutions with a computer search by Frye determining the smallest nontrivial solution 958004 2175194 4145604 4224814 4 5 Linear Diophantine equations EditOne equation Edit The simplest linear Diophantine equation takes the forma x b y c displaystyle 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 Bezout 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 havea x k v b y k u a x b y k a v b u a x b y k u d v v d u a x b y displaystyle begin aligned a x kv b y ku amp ax by k av bu amp ax by k udv vdu amp ax by end aligned showing that x kv y ku is another solution Finally given two solutions such that a x 1 b y 1 a x 2 b y 2 c displaystyle ax 1 by 1 ax 2 by 2 c one deduces that u x 2 x 1 v y 2 y 1 0 displaystyle u x 2 x 1 v y 2 y 1 0 As u and v are coprime Euclid s lemma shows that v divides x2 x1 and thus that there exists an integer k such that both x 2 x 1 k v y 2 y 1 k u displaystyle x 2 x 1 kv quad y 2 y 1 ku Therefore x 2 x 1 k v y 2 y 1 k u displaystyle x 2 x 1 kv quad y 2 y 1 ku which completes the proof Chinese remainder theorem Edit The Chinese remainder theorem describes an important class of linear Diophantine systems of equations let n 1 n k displaystyle n 1 dots n k be k pairwise coprime integers greater than one a 1 a k displaystyle a 1 dots a k be k arbitrary integers and N be the product n 1 n k displaystyle n 1 cdots n k The Chinese remainder theorem asserts that the following linear Diophantine system has exactly one solution x x 1 x k displaystyle x x 1 dots x k such that 0 x lt N and that the other solutions are obtained by adding to x a multiple of N x a 1 n 1 x 1 x a k n k x k displaystyle begin aligned x amp a 1 n 1 x 1 amp vdots x amp a k n k x k end aligned System of linear Diophantine equations Edit 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 writtenA X C displaystyle 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 matrixB b i j U A V displaystyle B b i j UAV 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 B V 1 X U C displaystyle B V 1 X UC Calling yi the entries of V 1 X and di those of D UC this leads to the system b i i y i d 1 1 i k 0 y i d i k lt i n displaystyle begin aligned amp b i i y i d 1 quad 1 leq i leq k amp 0y i d i quad k lt 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 bi i divides di for i k and di 0 for i gt k If this condition is fulfilled the solutions of the given system areV d 1 b 1 1 d k b k k h k 1 h n 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 hk 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 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 equations EditA 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 displaystyle 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 d th power of another rational number A witness of the difficulty of the problem is Fermat s Last Theorem for d gt 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 Falting 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 Degree two Edit 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 3 z 2 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 3 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 Geometric interpretation Edit Let Q x 1 x n 0 displaystyle Q x 1 ldots x n 0 be a homogeneous Diophantine equation where Q x 1 x n 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 x i displaystyle x i are zero If a 1 a n displaystyle a 1 ldots a n is a non trivial integer solution of this equation then a 1 a n displaystyle left a 1 ldots a n right are the homogeneous coordinates of a rational point of the hypersurface defined by Q Conversely if p 1 q p n q textstyle left frac p 1 q ldots frac p n q right are homogeneous coordinates of a rational point of this hypersurface where q p 1 p n displaystyle q p 1 ldots p n are integers then p 1 p n 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 k p 1 d k p n d 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 p i displaystyle p i It follows that solving the Diophantine equation Q x 1 x n 0 displaystyle Q x 1 ldots x n 0 is completely reduced to finding the rational points of the corresponding projective hypersurface Parameterization Edit Let now A a 1 a n displaystyle A left a 1 ldots a n right be an integer solution of the equation Q x 1 x n 0 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 a n 0 displaystyle a n neq 0 Then one may pass to the affine case by considering the affine hypersurface defined by q x 1 x n 1 Q x 1 x n 1 1 displaystyle q x 1 ldots x n 1 Q x 1 ldots x n 1 1 which has the rational point R r 1 r n 1 a 1 a n a n 1 a n 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 y i x i r i 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 x 2 r 2 t 2 x 1 r 1 x n 1 r n 1 t n 1 x 1 r 1 displaystyle begin aligned x 2 amp r 2 t 2 x 1 r 1 amp vdots x n 1 amp r n 1 t n 1 x 1 r 1 end aligned Substituting this in q one gets a polynomial of degree two in x1 that is zero for x1 r1 It is thus divisible by x1 r1 The quotient is linear in x1 and may be solved for expressing x1 as a quotient of two polynomials of degree at most two in t 2 t n 1 displaystyle t 2 ldots t n 1 with integer coefficients x 1 f 1 t 2 t n 1 f n t 2 t n 1 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 x 2 x n 1 displaystyle x 2 ldots x n 1 one gets for i 1 n 1 x i f i t 2 t n 1 f n t 2 t n 1 displaystyle x i frac f i t 2 ldots t n 1 f n t 2 ldots t n 1 where f 1 f n 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 F i t 1 t n 1 t 1 2 f i t 2 t 1 t n 1 t 1 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 f i displaystyle f i These quadratic polynomials with integer coefficients form a parameterization of the projective hypersurface defined by Q x 1 F 1 t 1 t n 1 x n F n t 1 t n 1 displaystyle begin aligned x 1 amp F 1 t 1 ldots t n 1 amp vdots x n amp 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 t 1 t n 1 displaystyle t 1 ldots t n 1 As F 1 F n displaystyle F 1 ldots F n are homogeneous polynomials the point is not changed if all ti are multiplied by the same rational number Thus one may suppose that t 1 t n 1 displaystyle t 1 ldots t n 1 are coprime integers It follows that the integer solutions of the Diophantine equation are exactly the sequences x 1 x n displaystyle x 1 ldots x n where for i 1 n x i k F i t 1 t n 1 d displaystyle x i k frac F i t 1 ldots t n 1 d where k is an integer t 1 t n 1 displaystyle t 1 ldots t n 1 are coprime integers and d is the greatest common divisor of the n integers F i t 1 t n 1 displaystyle F i t 1 ldots t n 1 One could hope that the coprimality of the ti could imply that d 1 Unfortunately this is not the case as shown in the next section Example of Pythagorean triples Edit The equation x 2 y 2 z 2 0 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 y t x 1 displaystyle y t x 1 Putting this in the circle equation x 2 y 2 1 0 displaystyle x 2 y 2 1 0 one gets x 2 1 t 2 x 1 2 0 displaystyle x 2 1 t 2 x 1 2 0 Dividing by x 1 results in x 1 t 2 x 1 0 displaystyle x 1 t 2 x 1 0 which is easy to solve in x x 1 t 2 1 t 2 displaystyle x frac 1 t 2 1 t 2 It follows y t x 1 2 t 1 t 2 displaystyle y t x 1 frac 2t 1 t 2 Homogenizing as described above one gets all solutions as x k s 2 t 2 d y k 2 s t d z k s 2 t 2 d displaystyle begin aligned x amp k frac s 2 t 2 d y amp k frac 2st d z amp 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 gt t gt 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 Diophantine analysis EditTypical questions Edit 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 Edit 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 17th and 18th centuries Edit 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 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 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 The smallest solution of this equation in positive integers is x 226153980 y 1766319049 see Chakravala method Hilbert s tenth problem Edit Main article Hilbert s tenth problem 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 Edit 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 Edit 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 Infinite Diophantine equations Edit An example of an infinite diophantine equation is n a 2 2 b 2 3 c 2 4 d 2 5 e 2 displaystyle 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 9 Compare this to n a 2 4 b 2 9 c 2 16 d 2 25 e 2 displaystyle n a 2 4b 2 9c 2 16d 2 25e 2 cdots which does not always have a solution for positive n Exponential Diophantine equations EditIf 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 2n 7 x2 and the equation of the Fermat Catalan conjecture and Beal s conjecture am bn ck with inequality restrictions on the exponents 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 Stormer s theorem or even trial and error See also EditKuṭṭaka Aryabhata s algorithm for solving linear Diophantine equations in two unknownsNotes Edit Quotations by Hardy Gap dcs st and ac uk Archived from the original on 16 July 2012 Retrieved 20 November 2012 Everest G Ward Thomas 2006 An Introduction to Number Theory Graduate Texts in Mathematics vol 232 Springer p 117 ISBN 9781846280443 a b Wiles Andrew 1995 Modular elliptic curves and Fermat s Last Theorem PDF Annals of Mathematics 141 3 443 551 doi 10 2307 2118559 JSTOR 2118559 OCLC 37032255 Elkies Noam 1988 On A4 B4 C4 D4 PDF Mathematics of Computation 51 184 825 835 doi 10 2307 2008781 JSTOR 2008781 MR 0930224 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 amp Business Media p 50 ISBN 978 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 ISBN 0 444 82949 0 Elsevier MIT Press Kovacic Jerald 8 May 1985 An Algorithm for Solving Second Order Linear Homogeneous Differential Equations PDF Core Archived PDF from the original on 16 April 2019 A320067 Oeis References EditMordell L J 1969 Diophantine equations Pure and Applied Mathematics Vol 30 Academic Press ISBN 0 12 506250 8 Zbl 0188 34503 Schmidt Wolfgang M 1991 Diophantine approximations and Diophantine equations Lecture Notes in Mathematics Vol 1467 Berlin Springer Verlag ISBN 3 540 54058 X Zbl 0754 11020 Shorey T N Tijdeman R 1986 Exponential Diophantine equations Cambridge Tracts in Mathematics Vol 87 Cambridge University Press ISBN 0 521 26826 5 Zbl 0606 10011 Smart Nigel P 1998 The algorithmic resolution of Diophantine equations London Mathematical Society Student Texts Vol 41 Cambridge University Press ISBN 0 521 64156 X Zbl 0907 11001 Stillwell John 2004 Mathematics and its History Second ed Springer Science Business Media Inc ISBN 0 387 95336 1 Further reading EditBachmakova Isabelle 1966 Diophante et Fermat Revue d Histoire des Sciences et de Leurs Applications 19 4 289 306 doi 10 3406 rhs 1966 2507 JSTOR 23905707 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 Arithmetic of Algebraic Curves from Diophantus to Poincare Historia Mathematica 8 1981 393 416 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 Dickson Leonard Eugene 2005 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 Rashed Roshdi Houzel Christian 2013 Les Arithmetiques de Diophante doi 10 1515 9783110336481 ISBN 978 3 11 033593 4 Rashed Roshdi Histoire de l analyse diophantienne classique D Abu Kamil a Fermat Berlin New York Walter de Gruyter External links EditDiophantine Equation From MathWorld at Wolfram Research Diophantine equations Encyclopedia of Mathematics EMS Press 2001 1994 Dario Alpern s Online Calculator Retrieved 18 March 2009 Retrieved from https en wikipedia org w index php title Diophantine equation amp oldid 1139623166, wikipedia, wiki, book, books, library,

article

, read, download, free, free download, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, picture, music, song, movie, book, game, games.