### Reduction of an indefinite binary quadratic form

Given an indefinite binary quadratic form ax^{2}+bxy+cy^{2}, 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^{2}-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 Φ_{0} = (a, b, c) and Φ_{i} = ((-1)^{i}A_{i}, B_{i}, (-1)^{i+1}A_{i+1}) for i ≥ 0, as follows:

Expand F_{0} = η as a simple continued fraction: η = [g_{0},g_{1},...] and define A_{i}, B_{i} and A_{i+1} by

F_{i} = (B_{i} + R)/2|A_{i+1}| = (P_{i} + R)/Q_{i}, B_{i}^{2} + 4A_{i}A_{i+1} = d,

where (P_{i} + R)/Q_{i} is the i-th complete convergent to η.
Then with s_{i} = sgn(A_{i+1}),

- F
_{i} = (-1)^{i}s_{i}/f_{i}, where f_{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)^{i}s_{i}g_{i}Y.

Eventually F_{i} will be reduced for some i and
(-1)^{i}s_{i}/f_{i} > 1, -1 < (-1)^{i}s_{i}/σ(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^{2} - dy^{2} = -4 has a solution.

*Last modified 8th December 2006*

Return to main page