numbers (version 0.8-5)

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

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

Arguments

d

non-square integer greater 1.

Author

Hans Werner Borchers

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 \(\sqrt{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.

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