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.

The algorithm:

  1. 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.
  2. 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.
  3. If each representation yields no solution, then the negative Pell equation is insoluble.
Enter a non-square D: (> 1)

Last modified 30th September 2006
Return to main page