Primitive Pythagorean triples and the construction of non-square d such that the negative Pell equation is soluble

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 x2 - dy2 = -1 to be soluble in positive integers.

(It is well-known that x2 - dy2 = -1 is soluble in positive integers, if and only if the length of the period of continued fraction of √d is odd.)

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) with a ≥ 0, b ≥ 0, and satisfying aA - bB = ±1.
(This satisfies a ≤ B/2, b ≤ A/2.)

We exhibit A, B, a, b, x and y.
We also print the fundamental solution η = (X, Y) of x2 - dy2 = -1 and the relation (x,y) = ηn.

See online paper.

Enter v (v > 0):
Enter u (u > v, one of u and v even, gcd(u,v)=1)):

Last modified 5th December 2013
Return to main page