The Florida 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.)

Write α/Δ₁ = r₁/r₂ and β/Δ₁ = s₁/s₂, where gcd(r₁/r₂) = 1 = gcd(s₁/s₂), and r₂ > 0, s₂ > 0.

Make a transformation r₂x = X + r₁, s₂y = Y + s₁.

Equation (1) transforms to AX² + BXY + CY² = M, (2)
where A = as₂², B = br₂s₂, C = cr₂² and M = -r₂²s₂²(ae² - bde + cd² + fΔ₁)/Δ₁.

Let gg = gcd(A, B, C). If gg does not divide M, there are not integer solutions of (1).

Otherwise replace (A, B, C, M) by (A/gg, B/gg, C/gg, M/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 ≤ k – 1, ε = ±1
to see if (x₀, y₀) = (X + r₁)/r₂, (Y + s₁) /s₂) is an integer solution of (1).

This gives a corresponding family

(r₂x_n, s₂y_n) = εU^{kn + j}(X_i, Y_i)^t + (r₁,s₁)^t, n ∈ ℤ

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

In Case 2, test (X,Y)^t = ε(-U)^j(X_i, Y_i)^t, 1 ≤ i ≤ g, 0 ≤ j ≤ k/2 – 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