The Legendre algorithm

Input: a, b, c, d, e, f, where Δ1 = b2 – 4ac > 0 and is not a square.

Problem: Find all integer solutions of ax2 + bxy + cy2 + dx + ey + f = 0. (1)

ν = (φ1 + ψ1√Δ1)/2 gives the least positive solution of u2 – Δ1v2 = 4.

κ = ενn = (φ + ψ√Δ1)/2, where ε = ±1, n ∈ ℤ.

v11 = (φ – bψ)/2,  v12 = -cψ, v21 = aψ,  v22 = (φ + bψ)/2.

α = 2cd – be,   β = 2ae – bd.

K1(κ) = (α – (αv11 + βv12))/Δ1 ,   K2(κ) = (β – (αv21 + βv22))/Δ1

Case 1. κ = ν, K1(ν) and K2(ν) are both integers.
Case 2. κ = -ν, Case 1 does not hold, but K1(-ν) and K2(-ν) are both integers.
Case 3. κ = ν2. Neither Case 1 nor Case 2 occurs. (We know K12) and K22) are both integers.)

Make a transformation Δ1x = X + α, Δ1y = Y + β.

equation (1) transforms to AX2 + BXY + CY2 = N, (2)
where A = a/gg, B = b/gg, C = c/gg, gg = gcd(a,b,c), and N = -Δ1(ae2 - bde + cd2 + fΔ1)/gg.

If equation (2) has no integer solutions, then neither does equation (1).

Suppose (2) has g fundamental solutions (Xi, Yi), 1 ≤ i ≤ g.

Δ2 = B2 – 4AC.

μ = (u1 + v1√Δ2)/2 gives the least positive solution of u2 – Δ2v2 = 4.

U = [(u1 – Bv1)/2,  -Cv1]
       [Av1,   (u1 + Bv1)/2]

Determine k ≥ 1 such that ν = μk.

In Case 3, test (X,Y)t = εUj(Xi, Yi)t, 1 ≤ i ≤ g, 0 ≤ j ≤ 2k-1, ε = ±1
to see if (x0, y0) = (X + α)/Δ1, (Y + β)/Δ1) is an integer solution of (1).

This gives a corresponding family

1xn, Δ1yn) = εUkn + j(Xi, Yi)t + (α, β)t, n ∈ ℤ

In Case 1, test (X,Y)t = εUj(Xi, Yi)t, 1 ≤ i ≤ g, 0 ≤ j ≤ k-1, ε = ±1

In Case 2, test (X,Y)t = ε(-U)j(Xi, Yi)t, 1 ≤ i ≤ g, 0 ≤ j ≤ k-1, ε = ±1

The families satisfy the recurrence relations

xn+1 = v11xn + v12yn + K1(κ),
yn+1 = v21xn + v22yn + K2(κ).

xn = v22xn+1 – v12yn+1 + K1-1),
yn = -v21xn+1 + v11yn+1 + K2-1).

Last modified 18th September 2022
Return to main page