### 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 x^{2} - dy^{2} = -1 to be soluble in positive integers.
(It is well-known that x^{2} - dy^{2} = -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. A^{2} + B^{2} = C^{2}) with gcd(A, B) = 1.

Without loss of generality, we assume A is even, B odd.

Let aA - bB = ±1; d = a^{2} + b^{2}. We see b is odd.

Then (x, y) = (aB + bA, C) satisfies x^{2} - dy^{2} = -1.

**Proof.**
dy^{2} = (a^{2} + b^{2})(A^{2} + B^{2}) = (aB + bA)^{2} + (aA - bB)^{2} = x^{2} + 1.

Our implementation starts with the general primitive Pythagorean triple solution with A even:
A = 2uv, B = u^{2} - v^{2}, C = u^{2} + v^{2},

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 x^{2} - dy^{2} = -1 and the relation (x,y) = η^{n}.

See online paper.

*Last modified 5th December 2013*

Return to main page