Solving the diophantine equation x2- Dy2=N, D > 0 and not a perfect square

This finds fundamental primitive solutions for the diophantine equation x2-Dy2=N, D > 0, D not a perfect square. We find the fundamental solutions for classes P with 0 ≤ P ≤ |N|/2, where P2 D (mod |N| ).

E=1 is verbose and prints partial and complete quotients, as well as convergents, up to the end of a period (or double period, in the case of odd period).

The algorithm goes back to Lagrange 1770 and should be better known, as it generalises the well-known continued fraction algorithm for solving Pell's equation. (See a slide-talk (pdf) by Keith Matthews.)

Another approach to the algorithm, using ideals and semi-regular continued fractions, was discovered by Richard Mollin - see Expositiones Math. 19 (2001) 55-73.)

The standard method is due to Gauss (See G.B. Mathews Number Theory, page 97 or note.)

The book L'equation diophantine du second degré by Alain Faisant, has an approach which seems to be a continued fraction version of Gauss' algorithm.

Enter D (< 1010):
Enter N (non-zero):
Enter E (0 or 1):

Last modified 10th September 2004
Return to main page