The Legendre algorithm

Problem: Find all integer solutions of ax² + bxy + cy² + dx + ey + f = 0. (1)

ν = (φ₁ + ψ₁√Δ₁)/2 gives the least positive solution of u² – Δ₁v² = 4.

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

v₁₁ = (φ – bψ)/2,  v₁₂ = -cψ, v₂₁ = aψ,  v₂₂ = (φ + bψ)/2.

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

K₁(κ) = (α – (αv₁₁ + βv₁₂))/Δ₁ ,   K₂(κ) = (β – (αv₂₁ + βv₂₂))/Δ₁

Case 1. κ = ν, K₁(ν) and K₂(ν) are both integers.
Case 2. κ = -ν, Case 1 does not hold, but K₁(-ν) and K₂(-ν) are both integers.
Case 3. κ = ν². Neither Case 1 nor Case 2 occurs. (We know K₁(ν²) and K₂(ν²) are both integers.)

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

equation (1) transforms to AX² + BXY + CY² = N, (2)
where A = a/gg, B = b/gg, C = c/gg, gg = gcd(a,b,c), and N = -Δ₁(ae² - bde + cd² + fΔ₁)/gg.

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

Suppose (2) has g fundamental solutions (X_i, Y_i), 1 ≤ i ≤ g.

Δ₂ = B² – 4AC.

μ = (u₁ + v₁√Δ₂)/2 gives the least positive solution of u² – Δ₂v² = 4.

U = [(u₁ – Bv₁)/2,  -Cv₁]
       [Av₁,   (u₁ + Bv₁)/2]

Determine k ≥ 1 such that ν = μ^k.

In Case 3, test (X,Y)^t = εU^j(X_i, Y_i)^t, 1 ≤ i ≤ g, 0 ≤ j ≤ 2k-1, ε = ±1
to see if (x₀, y₀) = (X + α)/Δ₁, (Y + β)/Δ₁) is an integer solution of (1).

This gives a corresponding family

(Δ₁x_n, Δ₁y_n) = εU^{kn + j}(X_i, Y_i)^t + (α, β)^t, n ∈ ℤ

In Case 1, test (X,Y)^t = εU^j(X_i, Y_i)^t, 1 ≤ i ≤ g, 0 ≤ j ≤ k-1, ε = ±1

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

The families satisfy the recurrence relations

x_n+1 = v₁₁x_n + v₁₂y_n + K₁(κ),
y_n+1 = v₂₁x_n + v₂₂y_n + K₂(κ).

x_n = v₂₂x_n+1 – v₁₂y_n+1 + K₁(κ^-1),
y_n = -v₂₁x_n+1 + v₁₁y_n+1 + K₂(κ^-1).

Last modified 18th September 2022
Return to main page