Testing the solubility of the negative Pell equation
Suppose D is a positive integer, not a perfect square. Then the negative Pell equation x2 - Dy2 = -1 is soluble if and only if D is expressible as D = a2 + b2, gcd(a, b) = 1, a and b positive, b odd and the diophantine equation -bV2 + 2aVW + bW2 = 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 dV2 - 2eVW - dW2 = 1, Kenneth Hardy, Kenneth S. Williams, Pacific Journal of Mathematics, 124 (1986) and is also contained in Pell's Equations X2 - mY2 = -1, -4 and Continued Fractions, Pierre Kaplan, Kenneth S. Williams, J. Number Theory, 23 (1986) 169-182.
See online paper.
- 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 = a2 + b2, gcd(a, b) = 1, a and b positive, b odd, test the solubility of -bV2 + 2aVW + bW2 = 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