The Grytczuk, Luca, Wojtowicz (GLW) construction over a range of u and v

In a paper The negative Pell equation and Pythagorean triples, Proc. Japan Acad., 76 (2000) 91-94, Aleksander Grytczuk, Florian Luca and Marek Wójtowicz gave a necessary and sufficient for the negative Pell equation to be soluble.

Sufficiency. Let (A,B,C) be a Pythagorean triple (ie. A2 + B2 = C2) with gcd(A, B) = 1.
Without loss of generality, we assume A is even, B odd.
Let aA - bB = ±1; d = a2 + b2. We see b is odd.

Then (x, y)=(aB + bA, C) satisfies x2 - dy2 = -1.

Proof

dy2 = (a2 + b2)(A2 + B2)
= (aB + bA)2 + (aA - bB)2 = x2 + 1.

Our implementation starts with the general primitive Pythagorean triple solution with A even:

A = 2uv, B = u2 - v2, C = u2 + v2,

where (u, v) satisfies gcd(u, v) = 1, u > v > 0 and one of u and v is even.

We find the smallest (a, b), a > 0, b > 0, satisfying aA - bB = ±1.
(This satisfies a ≤ B/2, b ≤ A/2.)

If b ≠ 1, usually (x, y) is the fundamental solution η of the negative Pell equation.

We test all (u, v) with v1 ≤ v ≤ v2, u1 ≤ u ≤ u2, v < u, gcd(u, v) = 1, one of u and v even.

Enter v1 (v1 > 0):
Enter v2 (v2 ≥ v1):
Enter u1 (u1 > v1):
Enter u2 (u2 ≥ u1):

Last modified 29th September 2006
Return to main page