Reduction of an indefinite binary quadratic form

Given an indefinite binary quadratic form ax2+bxy+cy2, 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=b2-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:
  1. (a, b, c) is reduced;
  2. 0 < b < R and 0 < R - b < 2|a| < R + b;
  3. 0 < b < R and 0 < R - b < 2|c| < R + b;
  4. 0 < τ < 1 < -σ(τ);
  5. -1 < σ(1/τ) < 0 and 1 < 1/τ, ie. 1/τ is a reduced quadratic irrational.
  6. -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 Φ0 = (a, b, c) and Φi = ((-1)iAi, Bi, (-1)i+1Ai+1) for i ≥ 0, as follows:

Expand F0 = η as a simple continued fraction: η = [g0,g1,...] and define Ai, Bi and Ai+1 by

Fi = (Bi + R)/2|Ai+1| = (Pi + R)/Qi,     Bi2 + 4AiAi+1 = d,

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

Then with si = sgn(Ai+1),

  1. Fi = (-1)isi/fi, where fi is the first root of Φi;
  2. Φi(x, y) is transformed into Φi+1(X, Y) by the unimodular substitution

    x = Y,    y = -X + (-1)isigiY.

Eventually Fi will be reduced for some i and

(-1)isi/fi > 1, -1 < (-1)isi/σ(fi) < 0 .

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

If n is the period-length of the continued fraction for Fi, 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 x2 - dy2 = -4 has a solution.

Last modified 8th December 2006
Return to main page