#### Testing the solubility of the negative Pell equation

Suppose D is a positive integer, not a perfect square. Then the negative Pell equation x^{2} - Dy^{2} = -1 is soluble if and only if D is expressible as D = a^{2} + b^{2}, gcd(a, b) = 1, a and b positive, b odd and the diophantine equation -bV^{2} + 2aVW + bW^{2} = 1 has a solution. (The case of solubility occurs for exactly one such (a,b).)
This result is contained in *On the solvability of the Diophantine equation dV*^{2} - 2eVW - dW^{2} = 1, Kenneth Hardy, Kenneth S. Williams, Pacific Journal of Mathematics, **124** (1986) and is also contained in *Pell's Equations X*^{2} - mY^{2} = -1, -4 and Continued Fractions, Pierre Kaplan, Kenneth S. Williams, J. Number Theory, **23** (1986) 169-182.

See online paper.

The algorithm:

- Find all expressions of D as a sum of two relatively-prime squares using Cornacchia's method. If none, exit - the negative Pell equation is not soluble.
- For each representation D = a
^{2} + b^{2}, gcd(a, b) = 1, a and b positive, b odd, test the solubility of -bV^{2} + 2aVW + bW^{2} = 1 using the Lagrange-Matthews algorithm. If soluble, exit - the negative Pell equation is soluble.
- If each representation yields no solution, then the negative Pell equation is insoluble.

*Last modified 30th September 2006*

Return to main page