(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. |
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 (a0,b0) a0 ≥ 0, b0 ≥ 0, satisfying a0A - b0B = ±1.
(This satisfies |a0| ≤ B/2, |b0| ≤ A/2.)
Then the general solution (a,b) is (a,b) = (a0 + tB, b0 + tA).
We exhibit A, B, a, b, x and y. Clearly d is not a perfect square.
We also print the fundamental solution (X, Y) of x2 - dy2 = -1.
Surprisingly, the solution (x,y) given by the construction often turns out to be (X, Y) if b ≠ 1.
Necessity. Grytczuk, Luca, Wojtowicz give two proofs. We give a third proof depending on the continued fraction expansion of √d, which exhibits a, b, A and B explicitly:
Suppose the continued fraction of √d has odd period l = 2n - 1.
Let Ai/Bi and (Pi + √d)/Qi denote the i-th convergent and complete quotients, respectively.
Then if a = Pn, b = Qn, A = 2Bn-1Bn-2, B = Bn-12 - Bn-22, C = Bn-12 + Bn-22, we have
(a) d = a2 + b2, b odd,
(b) aA - bB = (-1)n,
(c) A2 + B2 = C2, A even, B odd, gcd(A, B) = 1,
(d) X = Al-1 = aB + bA,
(e) Y = Bl-1 = C.
See online paper.
Last modified 14th July 2008
Return to main page