solvePellsEq: Solve Pell's Equation

In numbers: Number-Theoretic Functions

Solve Pell's Equation

Description

Find the basic, that is minimal, solution for Pell's equation, applying the technique of (periodic) continued fractions.

Usage

solvePellsEq(d)

Arguments

d	non-square integer greater 1.

Details

Solving Pell's equation means to find integer solutions (x,y) for the Diophantine equation

x^2 - d\,y^2 = 1

for d a non-square integer. These solutions are important in number theory and for the theory of quadratic number fields.

The procedure goes as follows: First find the periodic continued fraction for √{d}, then determine the convergents of this continued fraction. The last pair of convergents will provide the solution for Pell's equation.

The solution found is the minimal or fundamental solution. All other solutions can be derived from this one – but the numbers grow up very rapidly.

Value

Returns a list with components

x, y	solution (x,y) of Pell's equation.
plen	length of the period.
doubled	logical: was the period doubled?
msg	message either "Success" or "Integer overflow".

If 'doubled' was TRUE, there exists also a solution for the negative Pell equation

Note

Integer overflow may happen for the convergents, but very rarely. More often, the terms x^2 or y^2 can overflow the maximally representable integer 2^53-1 and checking Pell's equation may end with a value differing from 1, though in reality the solution is correct.

Author(s)

Hans Werner Borchers

References

H.W. Lenstra Jr. Solving the Pell Equation. Notices of the AMS, Vol. 49, No. 2, February 2002.

See the "List of fundamental solutions of Pell's equations" in the Wikipedia entry for "Pell's Equation".

See Also

periodicCF

Examples

  s = solvePellsEq(1003)                # $x = 9026, $y = 285
  9026^2 - 1003*285^2 == 1
  # TRUE

numbers documentation built on Nov. 23, 2022, 9:06 a.m.