Reduction of an indefinite binary quadratic form

Given an indefinite binary quadratic form ax²+bxy+cy², we use the PQa continued fraction algorithm to determine a reduced form and thence a cycle of reduced forms.
Our account is based on that in L.E. Dickson, Introduction to the theory of numbers pp. 99-105, Dover 1957, where the connection between a cycle of reduced forms and the periodic expansion of a reduced quadratic irrational is described. We generalise this, making use of the fact that the complete convergents of a quadratic irrational eventually become reduced.
There is another related algorithm (5.6.5) in Henri Cohen's book, A course in computational number theory, Edition 1, pp. 257-261.

Notation. d=b²-4ac > 0, d is not a perfect square, so ac ≠ 0. R = √d.
Dickson defines the first and second roots:

f = (R - b)/2a, σ(f) = (-R - b)/2a.

A form (a, b, c) is called reduced if |f| < 1 < |σ(f)| and fσ(f) < 0.

Let τ = (R - b)/2|a| and η = (R + b)/2|c|. Then the following are equivalent:

(a, b, c) is reduced;
0 < b < R and 0 < R - b < 2|a| < R + b;
0 < b < R and 0 < R - b < 2|c| < R + b;
0 < τ < 1 < -σ(τ);
-1 < σ(1/τ) < 0 and 1 < 1/τ, ie. 1/τ is a reduced quadratic irrational.
-1 < σ(η) < 0 and 1 < η, ie. η is a reduced quadratic irrational.

Note. If (a, b, c) is reduced, then ac < 0 and f and a have the same sign.
Also (c, b, a) is reduced.

We define a sequence of forms Φ₀ = (a, b, c) and Φ_i = ((-1)ⁱA_i, B_i, (-1)ⁱ⁺¹A_i+1) for i ≥ 0, as follows:

Expand F₀ = η as a simple continued fraction: η = [g₀,g₁,...] and define A_i, B_i and A_i+1 by A₀ = a, A₁ = -c, B₀ = b, and

F_i =(P_i + R)/Q_i = (B_i + R)/2A_i+1 if i > 0, F₀ = (b + R)/2|c|, B_i² + 4A_iA_i+1 = d,

where (P_i + R)/Q_i is the i-th complete convergent to η.

Then

F_i = (-1)ⁱ/f_i, where f_i = (-B_i + R)/2(-1)ⁱA_i is the first root of Φ_i;
Φ_i(x, y) is transformed into Φ_i+1(X, Y) by the unimodular substitution
x = Y, y = -X + (-1)ⁱg_iY.

Eventually F_i will be reduced for some i and

(-1)ⁱ/f_i > 1, -1 < (-1)ⁱ/σ(f_i) < 0 .

Hence |f_i| < 1 < |σ(f_i)|, f_iσ(f_i) < 0 and Φ_i is a reduced form.

If n is the period-length of the continued fraction for F_i, then

Φ_i, Φ_i+1,...,Φ_i+n-1

will be a cycle of forms if n is even, whereas if n is odd,

Φ_i, Φ_i+1,...,Φ_i+2n-1

will be a cycle of forms.

In the latter case, the Pell equation x² - dy² = -4 has a solution.

Last modified 31st January 2017
Return to main page