Finding the class number h(d) of a primitive binary quadratic forms of positive discriminant d

Finding the class number h(d) of primitive binary quadratic forms of positive discriminant d

Here d > 1, d ≡ 0 or 1 (mod 4), is not a perfect square.
We locate all reduced irrationals of the form (b+√d)/(2|c|), where c is negative and 4c divides d-b². We use the PQa continued fraction algorithm of Lagrange to break the set into disjoint cycles, retaining one number from each cycle.
Each reduced number then gives rise to a reduced form (a,b,c) of discriminant d, where a=(b²-d)/4c.
We are able to also determine if the Pell equation x²-dy²=-4 has a solution, by using the fact that the equation is soluble iff at least one of the above cycles is odd. If there is no solution, the reduced forms (-a,b,-c) have to be counted as well.

(See G.B. Mathews, Theory of Numbers, 80-81, note and Henri Cohen's A course in computational number theory, page 260, First Edition.)

Last modified 31st October 2006
Return to main page