Solving the diophantine equation x2- Dy2=N, D > 0 and not a perfect square
This finds the fundamental solutions, if any, of the diophantine equation x2-Dy2=N, D > 0, D not a perfect square. These are the solutions (a,b) in each equivalence class with least b ≥ 0, where we have a ≥ 0 if the class is ambiguous. If (x1,y1)is the least positive solution of Pell's equation, the solutions (x,y) in the class containing (a,b) are given by x+y√D = ±(a+b√D)(x1+y1√D)n, n ℇ ℤ.
We use T. Nagell's bounds for the fundamental solutions, which are, with small changes, sufficient as well as being necessary conditions.
See T. Nagell's Theory of Numbers, pages 204-212, BC program.
Note that this method is only useful for small D and N. In general, the LMM (Lagrange-Matthews-Mollin) method is the one to use - see CALC for a C version.
Warning: The program may halt prematurely, without an error message, due to running time limits.
If the Nagell upper bound exceeds 106, the program terminates after calculation of the least solution of Pell's equation.
We also produce a sequence of non-negative solutions (a,b), one from each equivalence class, with minimal b, using an algorithm of Frattini. See papers from The Jahrbuch database for Frattini's papers of 1891-2.
Last modified 6th March 2014
Return to main page