Pell's equation

Pell's equation for d  = 2 and six integer solutions

As Pell's equation (after John Pell , 1611-1685) is defined as a Diophantine equation of the form

${\ displaystyle x ^ {2} -dy ^ {2} = 1}$

with positive integer . ${\ displaystyle d}$

If it is a square number, then the equation obviously only has the trivial solutions . Otherwise there are an infinite number of solutions that can be determined using the continued fraction expansion of . The related equations and are also often called Pell's equations . ${\ displaystyle d}$${\ displaystyle (\ pm 1,0)}$${\ displaystyle {\ sqrt {d}}}$${\ displaystyle x ^ {2} -dy ^ {2} = - 1 \, \!}$${\ displaystyle x ^ {2} -dy ^ {2} = \ pm 4 \, \!}$

The equation is mistakenly attributed to John Pell. The name Fermat's equation would be more correct .

The equation was already known to Brahmagupta and Bhaskara II . The solution to this equation was posed as a problem by Pierre de Fermat in a letter to Bernard Frénicle de Bessy and published as a problem in 1657. Pell never bothered to solve the equation. Brouncker found some solutions (published in Commercium epistolicum of John Wallis in 1658). Leonhard Euler came across Brouncker's solution in the Latin edition of the Treatise of Algebra by John Wallis and incorrectly named the equation after Pell. Euler first published the Pell equation in 1732 and later found the connection with continued fractions (published in 1765), which is basically behind Brouncker's solution. After Euler, Joseph-Louis Lagrange studied the equation extensively and was the first to provide a proof that there is a solution for each , and Fermat possibly had a proof as well. ${\ displaystyle d}$

Algebraic Number Theory

Finding all solutions is equivalent to finding the units of the integral ring of the real-square number field for special ones. After the Dirichlet set unit has unit group to Rank 1 d. That is, there is a fundamental unit (or basic unit ) with which all solutions can be represented as . ${\ displaystyle d}$ ${\ displaystyle \ mathbb {Q} ({\ sqrt {d}})}$${\ displaystyle \ varepsilon = x_ {0} + {\ sqrt {d}} y_ {0},}$${\ displaystyle \ pm \ varepsilon ^ {n}, n \ in \ mathbb {Z}}$

For example, the unit is a fundamental unit , it corresponds to the solution x = 17, y = 12, and the other solutions can be generated from it. ${\ displaystyle d = 2}$${\ displaystyle 17-12 {\ sqrt {2}}}$

possible solutions

Solution with the help of continued fraction expansion

The continued fraction expansion of a quadratically irrational number is infinite and periodic. For example, the continued fraction expansion ${\ displaystyle {\ sqrt {d}}}$${\ displaystyle {\ sqrt {13}}}$

${\ displaystyle {\ sqrt {13}} = [3; {\ overline {1,1,1,1,6}}] \ ,.}$

If you break off the development at the point , you get starting with${\ displaystyle n}$${\ displaystyle n = 1}$

${\ displaystyle {\ sqrt {13}} \ approx {\ frac {3} {1}}, {\ frac {4} {1}}, {\ frac {7} {2}}, {\ frac {11 } {3}}, {\ frac {18} {5}} _ {n = 5}, {\ frac {119} {33}}, {\ frac {137} {38}}, {\ frac {256 } {71}}, {\ frac {393} {109}}, {\ frac {649} {180}} _ {n = 10}, {\ frac {4287} {1189}}, \ dots}$

and finds the places and the solutions ${\ displaystyle n = 5}$${\ displaystyle n = 10}$

${\ displaystyle x_ {0} = 18, y_ {0} = 5}$

from and ${\ displaystyle x ^ {2} -dy ^ {2} = - 1}$

${\ displaystyle x_ {1} = 649, y_ {1} = 180}$

from . ${\ displaystyle x ^ {2} -dy ^ {2} = 1}$

It is also found that for each element of the broken continued fraction expansion of length there is a solution to a Pell's equation with a right-hand side . ${\ displaystyle d = 13}$${\ displaystyle n = 5k, k \ in \ mathbb {N}}$${\ displaystyle \ pm 1}$

Generate further solutions based on a known

If a solution is known, further solutions can be determined with a matrix multiplication . It applies ${\ displaystyle x_ {0}, y_ {0}}$

${\ displaystyle {\ begin {pmatrix} x_ {i + 1} \\ y_ {i + 1} \ end {pmatrix}} = {\ begin {pmatrix} x_ {0} & dy_ {0} \\ y_ {0} & x_ {0} \ end {pmatrix}} {\ begin {pmatrix} x_ {i} \\ y_ {i} \ end {pmatrix}}}$
example

Pell's equation for has the minimal solution . The next solutions then arise to ${\ displaystyle d = 5}$${\ displaystyle (x_ {0} = 2, y_ {0} = 1)}$

${\ displaystyle {\ begin {pmatrix} x_ {1} \\ y_ {1} \ end {pmatrix}} = {\ begin {pmatrix} 2 & 5 \\ 1 & 2 \ end {pmatrix}} {\ begin {pmatrix} 2 \ \ 1 \ end {pmatrix}} = {\ begin {pmatrix} 9 \\ 4 \ end {pmatrix}}}$
${\ displaystyle {\ begin {pmatrix} x_ {2} \\ y_ {2} \ end {pmatrix}} = {\ begin {pmatrix} 2 & 5 \\ 1 & 2 \ end {pmatrix}} {\ begin {pmatrix} 9 \ \ 4 \ end {pmatrix}} = {\ begin {pmatrix} 38 \\ 17 \ end {pmatrix}}}$

etc.

${\ displaystyle {\ sqrt {d}}}$has the continued fraction expansion (see Continued Fraction # Periodic Continued Fractions ). Let with integers , then is the smallest solution of the generalized Pell's equation . As mentioned, the other solutions can be constructed from this. ${\ displaystyle {\ sqrt {d}} = [b_ {0}; {\ overline {b_ {1}, \ dotsc, b_ {m}}}]}$${\ displaystyle {\ frac {x} {y}} = [b_ {0}; b_ {1}, \ dotsc, b_ {m-1}]}$${\ displaystyle x, y}$${\ displaystyle x, y}$${\ displaystyle x ^ {2} -dy ^ {2} = {(- 1)} ^ {m}}$

Archimedes' cattle problem

When solving Archimedes' cattle problem , one comes across (if one calculates skillfully) Pell's equation for the parameter , which is the minimal solution ${\ displaystyle x ^ {2} -d \ cdot y ^ {2} = 1}$${\ displaystyle d = 4729494}$

${\ displaystyle x = 109931986732829734979866232821433543901088049 \ approx 1 {,} 099 \ cdot 10 ^ {44}}$
${\ displaystyle y = 50549485234315033074477819735540408986340 \ approx 5 {,} 055 \ cdot 10 ^ {40}}$

Has. For the cattle problem, however, you don't need the minimum solution, but rather a (more precisely: the smallest) solution where is a multiple of . ${\ displaystyle y}$${\ displaystyle 2 \ cdot 4657}$

Alternatively, you can search for the minimum solution (now without secondary conditions) for Pell's equation with parameters , which is of the following order of magnitude (see above source): ${\ displaystyle d = 410286423278424 = (2 \ cdot 4657) ^ {2} \ cdot 4729494}$

${\ displaystyle x \ approx 3 {,} 7653 \ cdot 10 ^ {103272}}$
${\ displaystyle y \ approx 1 {,} 8589 \ cdot 10 ^ {103265}}$

It is not by chance what numerically establishes the relationship between the minimal solutions of Pell's two equations. ${\ displaystyle 2 \ cdot 3 {,} 7653 \ cdot 10 ^ {103272} \ approx (2 \ cdot 1 {,} 0993199 \ cdot 10 ^ {44}) ^ {2329}}$

For the cattle problem itself, the number is important as an intermediate result . The end result is times that, i.e. approx . ${\ displaystyle 4657 \ times 957 \ times y ^ {2} \ approx 1 {,} 5401 \ times 10 ^ {206537}}$${\ displaystyle 50389082}$${\ displaystyle 7 {,} 760 \ cdot 10 ^ {206544}}$

literature

• HW Lenstra Jr .: Solving the Pell Equation , Notices of the American Mathematical Society, Volume 49, Issue 2, 2002, pp. 182-192, online (PDF; 237 kB).
• MJ Jacobson Jr., HC Williams: Solving the Pell Equation , CMS Books in Mathematics, Springer 2009, ISBN 978-0-387-84922-5
• Leonard Dickson : History of the theory of numbers , Washington DC: Carnegie Institution, 1920, Chapter 12 (on the history of Pell's equation)